21
\$\begingroup\$

Background

A Jordan matrix is a block-diagonal matrix where each block on the diagonal has the structure of

$$ \begin{bmatrix} \lambda & 1 & 0 & \cdots & 0 \\ 0 & \lambda & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & 0 & \lambda \end{bmatrix} $$

where all values of \$\lambda\$ are identical inside each block. (A block diagonal matrix is one that can be divided into blocks, so that the blocks on the main diagonal are square and those out of the main diagonal are all zeros. See examples below.)

The following are some examples of a Jordan matrix:

$$ J_1=\left[\begin{array}{c|c|cc} 2 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 2 \end{array}\right]\\ J_2=\left[\begin{array}{ccc|cc|cc|ccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 3 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 7 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 7 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 7 \end{array}\right] $$

The following are more examples of Jordan matrices:

[[0]]  // 1x1 matrix is always Jordan

[[0, 0],
 [0, 0]]  // all-zero matrix is also always Jordan

[[3, 0, 0],
 [0, 2, 0],
 [0, 0, 2]]  // diagonal matrix is also Jordan, even if it has duplicates

[[3, 0, 0],
 [0, 2, 1],  // the one between the two 2s is optional
 [0, 0, 2]]  // (if it is a zero, the two are in separate blocks)

[[99,  1,  0,  0],
 [ 0, 99,  1,  0],
 [ 0,  0, 99,  0],
 [ 0,  0,  0,  1]]  // the matrix may contain numbers >= 10

[[1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 3, 1, 0],  // same diagonal entries may appear separately
 [0, 0, 0, 3, 0],
 [0, 0, 0, 0, 1]]

The following are not Jordan:

[[0, 0, 0],
 [0, 0, 0],
 [1, 0, 0]]  // has a one where it should be zero

[[2, 0, 0],
 [1, 2, 0],
 [0, 0, 1]]  // 1 is at the wrong side of the diagonal

[[1, 1, 0],
 [0, 2, 0],  // the numbers on the left of and below the
 [0, 0, 2]]  // non-diagonal 1 are not equal

[[99, 99,  0,  0],
 [ 0, 99, 99,  0],
 [ 0,  0, 99,  0],
 [ 0,  0,  0,  1]]  // the matrix may contain numbers >= 10

[[1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 3, 2, 0],  // all numbers right above the main diagonal
 [0, 0, 0, 3, 0],  // should be either 0 or 1
 [0, 0, 0, 0, 1]]

Challenge

Given a square matrix filled with non-negative integers, determine if it is a Jordan matrix.

Input format is flexible. For output, you can choose to

  1. output truthy/falsy using your language's convention (swapping is allowed), or
  2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
4
  • \$\begingroup\$ is it ok to take as input the size of the matrix? And is ik ok to take the matrix on the form of the concatenation of all the raw in one single array/string? \$\endgroup\$
    – Jakque
    Jul 20, 2021 at 10:05
  • \$\begingroup\$ @Jakque Yes, flattened matrix with dimensions is a valid I/O method by default. \$\endgroup\$
    – Bubbler
    Jul 20, 2021 at 11:14
  • 3
    \$\begingroup\$ Can the input matrix contain integers >= 10? If so, could you add a test case with multi-digit integers? There's at least one answer that assumes single-digit. \$\endgroup\$
    – DLosc
    Jul 20, 2021 at 18:48
  • 1
    \$\begingroup\$ @DLosc Good point. I added one truthy and one falsy test case containing multi-digit numbers. \$\endgroup\$
    – Bubbler
    Jul 20, 2021 at 23:55

10 Answers 10

10
\$\begingroup\$

JavaScript, 58 bytes

a=>a.some((r,y)=>r.some((c,x)=>(r/(r=c)==a[x][x])/-y--<c))

Try it online!

  • When c==0
    • r/(r=c) is NaN or Infinity;
    • (r/(r=c)==a[x][x]) is false
    • (r/(r=c)==a[x][x])/-y-- is 0 or NaN
    • (r/(r=c)==a[x][x])/-y--<c is false
  • When y==0 (cells on main diagonal) and c>=1
    • (r/(r=c)==a[x][x])/-y-- is NaN or Infinity
    • (r/(r=c)==a[x][x])/-y--<c is false
  • When y==-1 (cells on right side of main diagonal) and c==1
    • r/(r=c) equals to r equals to left cell,
    • (r/(r=c)==a[x][x]) test if left cell equals to bottom cell
    • (r/(r=c)==a[x][x])/-y-- is 1 or 0 based on whether left cell equals to bottom cell
    • (r/(r=c)==a[x][x])/-y--<c is true if left cell not equals to right cell
  • When y==-1 (cells on right side of main diagonal) and c>=2
    • (r/(r=c)==a[x][x])/-y-- is 1 or 0
    • (r/(r=c)==a[x][x])/-y--<c is true
  • When (y<-1 or y>0) and c>=1
    • (r/(r=c)==a[x][x])/-y-- is a number in range [-Inf, 1)
    • (r/(r=c)==a[x][x])/-y--<c is true
\$\endgroup\$
7
\$\begingroup\$

Jelly, 14 13 bytes

ŒDµḢ=Ɲo@ƑḢ>FẠ

Try it online!

-1 because I actually thought to check if the input can contain negative integers

ŒDµ              Consider the diagonals of the input matrix.
   Ḣ             Pop the main diagonal;
     Ɲ           for each pair of its adjacent elements
    =            are they equal?
                 (Especially note that this results in a list of ones and zeroes,
                 of the same length as the superdiagonal.)
         Ḣ       Pop the superdiagonal;
      o@         are the logical ORs of its elements and the neighbor equalities
        Ƒ        equal to the neighbor equalities?
           F     For every element in the flattened remaining diagonals,
          > Ạ    is the test result strictly greater?

Jelly's logical OR is Python's: if the first argument is truthy it is returned, else the second argument is returned. Testing the diagonal equalities' invariance under flipped logical OR with the superdiagonal determines if every element of the superdiagonal is either a 0 anywhere or a 1 "between" two equal elements on the diagonal, since a 0 on the superdiagonal leaves either equality value unchanged, but any non-zero overrides the equality value--passing only if both are 1.

\$\endgroup\$
5
\$\begingroup\$

Rattle, 111 bytes

|sI^>s[[PgI#1I#s2=#-#1[^0[^1g2[^0=q]][1g2[^0[^1=q]P=#4<s<=#3-sg0>I~<I~s_3P=#4+<s<=#3sg0>I~<I~<[^~=q]]]]g1]`]`=1

Try it Online!

Needless to say, Rattle is not built to handle matrices and this approach is pretty brute-force. However, this code really shows off most of Rattle's features!

Explanation

|                      takes input and parses automatically (Rattle's parser is very
                        powerful and automatically recognises nested lists)
 s                     saves the list to the first memory slot (slot 0)
  I^                   gets the length of the list
    >                  move pointer right
     s                 save length of list to slot 1
      [[ ... ]`]`      nested loop to iterate over array
                 
(inside nested loop)
I won't explain every single command here but the code inside the nested loop is split
 into two parts. 
First, the code checks to make sure all values that are not on the diagonal or off 
 the diagonal to the right are all zero and all values off the diagonal to the right
 are 1 ​or 0. If not, it prints a falsy value (0).
Next, it iterates over all values of 1 which appear in the off-diagonal. For each
 value of 1 in this off-diagonal, it ensures the value to the left and below the 1
 are equal. If not, it prints a falsy value (0).
Knowing these conditions have been checked for, a truthy value (1) is printed if a
 falsy value has not already been printed.
\$\endgroup\$
4
\$\begingroup\$

R, 96 93 83 75 67 bytes

function(m,k,j=1:k^2%%(k+1),x=m[!j])any(m[j>1],diff(diag(m))&x,x>1)

Try it online!

Takes input as matrix and it's size.

Outputs inverted TRUE/FALSE values.

\$\endgroup\$
4
\$\begingroup\$

Python 3, 69 bytes

lambda m,n:re.sub(f"(.)({10**~-n}\\1)*(0%r|$)"%{n},"",m)>""
import re

Try it online!

input is a flatened string of the matrix and its size

output False for Jordan and True for not jordan

Edit:

as it wasn't specified when I post this answer, my solution only works for matrix with single digits elements

How it works:

  • the main idea i to substitute every "jordan" sub patern by the empty string and check if the result is the empty string (every subpart of the matrix was jordan)

  • (.)({10**~-n}\\1)*(0%r|$)"%{n} with for example n=4 will give the patern /(.)(1000\1)*(0{4}|$)/

\$\endgroup\$
2
\$\begingroup\$

Wolfram Mathematica, 150 144 137 69 bytes

With[{m=#,l=Length@#,d=Diagonal},Union@@Join[m~d~#&/@2~Range~l~Join~-Range@l,{If[#2==1,#1,#2]}&~MapThread~{Differences@d@m,m~d~1}]=={0}]&

I know... I don't like it either! But this was the shortest code that I could think of, and I'm definitely not an expert. Please take it with a huge grain of salt and enlighten me with your valuable suggestions. Try it online!

Edit later- Michael E2 proposed this elegant, much shorter solution: Try it online

IdentityMatrix@Length@#==ReverseSort@Abs@First@JordanDecomposition@#&

Explanation for the initial code:

(* The Diagonal method extracts diagonal vectors from input matrix *)
With[{m=#, l=Length@#, d=Diagonal},
Union@@(
(* Except for the main diagonal and the one above it,
   all other diagonals must be zero: *)
d[m,#]& /@ Complement[Range[-l,l],{0,1}]
(* These diagonals are combined by Union method above *)
)=={0}
&&
(* The Difference of elements of the main diagonal is calculated.
   If an element in the secondary diagonal is 1,
   its corresponding element in the difference diagonal must be zero *)
And@@
MapThread[If[#1==1,#2==0,#1==0]&, {d[#,1], Differences@ d[#]}]]&
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I'm surprised it doesn't have an IsJordanMatrix[] builtin for once \$\endgroup\$
    – user253751
    Jul 20, 2021 at 16:35
  • 3
    \$\begingroup\$ @user253751 actually, the correct syntax would have been JordanMatrixQ[] ;) \$\endgroup\$ Jul 20, 2021 at 17:56
  • 1
    \$\begingroup\$ There is Last@JordanDecomposition which computes the Jordan matrix corresponding to the input ... but the rows and columns appear in a particular order which might not match the input. \$\endgroup\$ Jul 20, 2021 at 22:09
  • \$\begingroup\$ I was trying to figure out if there might be a linear algebra test to determine if a matrix is in Jordan form, but couldn't come up with one. \$\endgroup\$
    – theorist
    Jul 20, 2021 at 23:10
2
+300
\$\begingroup\$

Desmos, 90 bytes

I=wy+x-w
f(L,w)=\prod_{x=1}^w\prod_{y=1}^w\{L[I]=0,x=y,x=y+1:\{L[I]=1\}\{L[I-1]=L[I+w]\}\}

Takes input as the flattened matrix and its width. Returns 1 for truthy and NaN for falsy.

Try it on Desmos!

Explanation

f(L,w)=
  \prod_{x=1}^w\prod_{y=1}^w   # iterate over all x,y in matrix
  \{ # piecewise (case statement)
    L[I]=0, # any 0 is OK; multiply by 1
    x=y,    # any values on main diagonal are OK; multiply by 1
    x=y+1:  # immediately above the main diagonal 
      \{L[I]=1\}           # must have value 1 (0s matched L[I]=0) and
      \{L[I-1]=L[I+w]\}    # left and bottom are same
    # fall through: multiply by NaN
  \}
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 27 bytes

⬤θ⬤ι∨¬λ∨⁼κμ∧⁼⊕κμ⁼λ⁼§ιꧧθμμ

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for Jordon, nothing if not. Explanation:

 θ                          Input array
⬤                           Each row satisfies
   ι                        Current row
  ⬤                         Each cell satifies
      λ                     Current cell
     ¬                      Logical Not i.e. is zero
    ∨                       Logical Or
         κ                  Current row index
        ⁼                   Equal to
          μ                 Current column index
       ∨                    Logical Or
              κ             Current row index
             ⊕              Incremented
            ⁼               Equal to
               μ            Current column index
           ∧                Logical And
                 λ          Current value
                ⁼           Equals
                   §ικ      Value to left
                  ⁼         Equals
                      §§θμμ Value below

Since the Equals operator returns 1 or 0, the penultimate equality only holds for 1s where the two adjacent values on the main diagonal are equal or 0s where the values are unequal, but if the value was 0 we skipped it earlier anyway.

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

PARI/GP, 57 bytes

m->matrix(#m,,i,j,[1+k=i-j,1-a=m[i,j],m[i,i]-m[j,j]]*a*k)

Attempt This Online!

Outputs a zero matrix when the input is a Jordan matrix. In PARI/GP's convention, a matrix is truthy if and only if it contains at least one truthy entry.

\$\endgroup\$
0
\$\begingroup\$

Python 3, 92 bytes

def f(m,w,h):
 for i in range(h-1):i*=w;m[i:i+2]=(m[i]==m[i-~w])<m[i+1],
 return any(m[:-1])

Attempt This Online!

This is longer than the earlier Python solution, but it supports numbers larger than 9, as required by the challenge. It takes the matrix as a flat list/array of integers in row-major order, and returns False if it's Jordan, True if not.

The loop tests that each triple of diagonal and superdiagonal entries follows the rules, and the diagonals are overwritten with the results. Then any checks both that those tests passed and that the rest of the matrix is zero.

This is the first time in my life that I've wanted comparison operators to be left-associative. I almost rewrote the answer in C just for that reason, but I looked it up, and it turns out < and == have different precedence in C, and <'s precedence is higher, which is the opposite of what I need. So much for that.

\$\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.