18
\$\begingroup\$

There's a type of n×n matrix W called the basic Weyr canonical form. Such a matrix is described by its blocks and has the following properties, using the following reference diagram:

enter image description here

  • the main diagonal blocks Wii are ni×ni matrices of the form λIni where Ini is the ni×ni identity matrix.
  • n1 ≥ n2 ≥ ... ≥ nr
  • the first superdiagonal blocks Wk-1,k for k ∈ 2..r are nk-1×nk matrices that are full column rank in row-reduced echelon form, or more simply put, Ink sitting on top of nk-1 - nk rows of zeros.
  • all other blocks are 0 matrices.

For example:

Weyr form

  • The main diagonal blocks (yellow) are such that the ni are 4, 2, 2, and 1.
  • The first superdiagonal blocks are in green.
  • The grey zone consists of all the other blocks, which are all 0.

For this challenge we will assume λ=1.

Input

A square matrix with 0s and 1s in any convenient format.

Output

Output one of two distinct values for whether the input matrix is Weyr or not Weyr.

Rules

This is . Fewest bytes in each language wins. Standard rules/loopholes apply.

Test cases

Presented as arrays of rows.

Weyr:

[[1]] 
[[1,1],[0,1]] 
[[1,0,1,0,0],[0,1,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[0,0,0,0,1]]
[[1,0,0,1,0,0,0,0,0],[0,1,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,0],[0,0,0,1,0,0,1,0,0],[0,0,0,0,1,0,0,1,0],[0,0,0,0,0,1,0,0,1],[0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,1]]
[[1,0,0,0,1,0,0,0,0],[0,1,0,0,0,1,0,0,0],[0,0,1,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,1,0,0],[0,0,0,0,0,1,0,1,0],[0,0,0,0,0,0,1,0,1],[0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,1]]

Non-Weyr:

[[0]]
[[1,0],[1,1]]
[[1,0,0,1,0,0],[0,1,0,0,0,0],[0,0,1,0,0,1],[0,0,0,1,0,0],[0,0,0,0,1,0],[0,0,0,0,0,1]]
[[1,0,1,0,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,1,0],[0,0,0,0,1]]
[[1,0,0,1,0,0,0,0,0],[0,1,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,0],[0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,1,0,0],[0,0,0,0,0,1,0,1,0],[0,0,0,0,0,0,1,0,1],[0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,1]]
\$\endgroup\$
  • 2
    \$\begingroup\$ Your definition of weyr, matrix is very unclear. In order to understand it I needed to first read the definition from wikipedia (which is not very clear either) and even then your definition is rather vague and ambiguous. For one I would make it clearer what n<sub>i</sub> is and what it is mean to do, currently it is not very clear that a matrix is weyr if such ns exist and rather it seems like they are some property of the matrix. \$\endgroup\$ – Sriotchilism O'Zaic May 30 '18 at 19:07
  • \$\begingroup\$ Is it correct that the identity matrix is a Weyr-matrix? \$\endgroup\$ – Stewie Griffin May 30 '18 at 19:43
  • \$\begingroup\$ The identity matrix is be a Weyr matrix with r = 1 and n_1 = n, so yes, albeit a degenerate one. \$\endgroup\$ – S.Klumpers May 30 '18 at 20:10
  • 2
    \$\begingroup\$ Suggested test case: [[1,0,0,1,0,0,0,0,0],[0,1,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,0],[0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,1,0,0],[0,0,0,0,0,1,0,1,0],[0,0,0,0,0,0,1,0,1],[0,0,0,0,0,0,0,1,0],[0,0,0,0,0,0,0,0,1]]. I think it's falsy (but my answer fails to identify it as such). \$\endgroup\$ – Arnauld May 30 '18 at 21:43
  • \$\begingroup\$ The definitions you included suggest you only want to identify basic weyr matrices, and not general weyr matrices. Is this what you intended for this challenge? \$\endgroup\$ – S.Klumpers May 31 '18 at 6:58
2
\$\begingroup\$

K (ngn/k), 91 88 84 80 bytes

{x~e|(-n)#'(0*x),'(!n)=\:,/(-1_b)+1_0{x#!y}':|-n-':|b:|\@[-1++/|\|+x|e:=n:#x]\0}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 2, 270 bytes

lambda m,w=0:{w}&{0,len(m)}and I(m)or any(I([l[:i]for l in m[:i]])*I([l[i:j+i]for l in m[:j]])*(sum(sum(m[:i]+[l[:i]for l in m],[]))==2*i+j)and f([l[i:]for l in m[i:]],j)for i in range(w,len(m))for j in range(1,i+1))
I=lambda m:all(sum(l)==l[i]>0for i,l in enumerate(m))

Try it online!

Explanation:

Recursively checks blocks for identity and their superdiagonal blocks.

I checks if a matrix is an identity matrix

I=lambda m:all(sum(l)==l[i]>0for i,l in enumerate(m))

For each block of the input matrix, the function checks that it is an identity, and that there is another identity matrix block, to it's right. The next iteration then looks at a block of that size.

{w}&{0,len(m)}and I(m)                # if the while matrix is an identity matrix,
                                      # return true (but only the first time or last block)
or
any(
 I([l[:i]for l in m[:i]])                         # the current block is identity
 *I([l[i:j+i]for l in m[:j]])                     # and, the smaller block to the right is identity
 *(sum(sum(m[:i]+[l[:i]for l in m],[]))==2*i+j)   # and everything below and to the right (not the
                                                  # smaller block), are 0
 and f([l[i:]for l in m[i:]],j)                   # and the remaining matrix is alse Weyr(recursively)
 for i in range(w,len(m))             # for each block size i
 for j in range(1,i+1)                # for each smaller right block of size j
)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.