19
\$\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 at 10:05
  • \$\begingroup\$ @Jakque Yes, flattened matrix with dimensions is a valid I/O method by default. \$\endgroup\$
    – Bubbler
    Jul 20 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 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 at 23:55
9
\$\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\$

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

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\$
1
\$\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 at 16:35
  • 2
    \$\begingroup\$ @user253751 actually, the correct syntax would have been JordanMatrixQ[] ;) \$\endgroup\$ Jul 20 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 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 at 23:10
0
\$\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\$

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.