Check if a matrix is a Toeplitz matrix

Question

You will be given a two-dimensional array and a number and you are asked to find whether the given matrix is Toeplitz or not. A matrix is a Toeplitz matrix if every descending diagonal, going from left to right, has only one distinct element. That is, it should be in the form:

Input Format:

You will be given a function which will take two-dimensional matrix as argument.

Output Format:

Return 1 from the function if the matrix is Toeplitz, else return -1.

Constraints:

3 < n,m < 10,000,000

where n is the number of rows while m will be the number of columns.

Sample Test Case:

Sample Input :
4 
5
6 7 8 9 2
4 6 7 8 9
1 4 6 7 8
0 1 4 6 7 

Sample Output : 
1 

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

Mathematica, 42 bytes

2Boole[#==ToeplitzMatrix[#&@@@#,#&@@#]]-1&

Mathematica doesn't have a built-in to check whether something is a Toeplitz matrix, but it does have a built-in to generate one. So we generate one from the first column (#&@@@#) and the first row (#&@@#) of the input and check whether it's equal to the input. To convert the True/False result to 1/-1 we use Boole (to give 1 or 0) and then simply transform the result with 2x-1.

Answer 2

Octave, 30 bytes

I'm assuming I don't have to handle 1,000,000x1,000,000 matrices as it says in the challenge. This works for matrices that don't exceed the available memory (less than 1 TB in my case).

@(x)x==toeplitz(x(:,1),x(1,:))

Try it online!

This takes a matrix x as input and creates a Toeplitz matrix based on the values on the first column, and the first row. It will then check each element of the matrices for equality. IF all elements are equal then the input is a Toeplitz matrix.

The output will be a matrix of the same dimensions as the input. If there are any zeros in the output then that's considered falsy be Octave.

Edit:

Just noticed the strict output format:

This works for 41 bytes. It might be possible to golf off a byte or two from this version, but I hope the output rules will be relaxed a bit.

@(x)2*(0||(x==toeplitz(x(:,1),x(1,:))))-1

Answer 3

Jelly, 5 bytes

ŒDE€Ạ

Try it online!

Following the definition here.

ŒDE€Ạ
ŒD     all diagonals
   €   for each diagonal ...
  E       all elements are equal
    Ạ  all diagonal return true

Answer 4

05AB1E, 11 bytes

Œ2ùvy`¦s¨QP

Try it online!

Explanation

Π            # get all sublists of input
 2ù           # keep only those of length 2
   v          # for each such pair
    y`        # split to separate lists
      ¦       # remove the first element of the second list
       s¨     # remove the last element of the first list
         Q    # compare for equality
          P   # product of stack

Answer 5

Haskell, 43 bytes

f(a:b:t)|init a==tail b=f$b:t|1>0= -1
f _=1

Try it online!

Answer 6

Mathematica, 94 bytes

l=Length;If[l@Flatten[Union/@Table[#~Diagonal~k,{k,-l@#+1,l@#[[1]]-1}]]==l@#+l@#[[1]]-1,1,-1]&

input

{{6, 7, 8, 9, 2}, {4, 6, 7, 8, 9}, {1, 4, 6, 7, 8}, {0, 1, 4, 6, 7}}

another one based on Stewie Griffin's algorithm

Mathematica, 44 bytes

If[#==#[[;;,1]]~ToeplitzMatrix~#[[1]],1,-1]&

Answer 7

Java 7, 239 233 220 113 bytes

int c(int[][]a){for(int i=a.length,j;i-->1;)for(j=a[0].length;j-->1;)if(a[i][j]!=a[i-1][j-1])return -1;return 1;}

-107 bytes after a tip of using a more efficient algorithm thanks to @Neil.

Explanation:

Try it here.

int c(int[][]a){                // Method with integer-matrix parameter and integer return-type
  for(int i=a.length,j;i-->1;)  //  Loop over the rows (excluding the first)
    for(j=a[0].length;j-->1;)   //   Loop over the columns (excluding the first)
      if(a[i][j]!=a[i-1][j-1])  //    If the current cell doesn't equal the one top-left of it:
        return -1;              //     Return -1
                                //   End of columns loop (implicit / single-line body)
                                //  End of rows loop (implicit / single-line body)
  return 1;                     //  Return 1
}                               // End of method

Answer 8

Haskell, 51 bytes

t takes a list of lists of integers and returns an integer.

t m=1-sum[2|or$zipWith((.init).(/=).tail)=<<tail$m]

Try it online!

This could have been 39 or 38 bytes with truthy/falsy output.

The idea to use init was inspired by Emigna's 05AB1E answer, which uses a very similar method; before that I used a nested zipping.

How it works

• zipWith((.init).(/=).tail)=<<tail is a point-free form of \m->zipWith(\x y->tail x/=init y)(tail m)m.
• This combines each consecutive pair of rows of m, checking if the first with first element removed is different from the second with second element removed.
• The or then combines the checks for all pairs of rows.
• 1-sum[2|...] converts the output format.

Answer 9

Husk, 6 4 bytes

ΛE∂↔

Try it online!

-2 bytes from Zgarb.

My first Husk answer! (Language Of The Month)

Takes matrix as command line argument.

Returns length of longest diagonal for true, and 0 otherwise.

Explanation

ΛE∂↔
   ↔ reverse the rows
  ∂  get antidiagonals
Λ    Check if all elements satisfy condition:
 E   Are all the elements equal?

Answer 10

JavaScript (ES6), 65 54 bytes

a=>a.some((b,i)=>i--&&b.some((c,j)=>c-a[i][j-1]))?-1:1

Answer 11

Ruby, 54 bytes

->a,b,m{m.reduce{|x,y|x[0..-2]==y[1,b]?y:[]}.size<=>1}

Exactly as specified, can be golfed more if flexible input/output is accepted.

Explanation:

Iterate on the matrix, and compare each line with the line above, shifted by one to the right. If they are different, use an empty array for the next iteration. At the end, return -1 if the final array is empty, or 1 if it's at least 2 elements (since the smallest possible matrix is 3x3, this is true if all comparisons return true)

Try it online!

Answer 12

PHP, 70 bytes

<?=!preg_match('/\[([\d,]+?),\d+\],\[\d+,(?!\1)/',json_encode($_GET));

Answer 13

Python, 108

r=range
f=lambda x,n,m:all([len(set([x[i][j] for i in r(n) for j in r(m) if j-i==k]))==1 for k in r(1-n,m)])

Not efficient at all since it touches every element n+m times while filtering for diagonals. Then checks if there are more than one unique element per diagonal.

Answer 14

Axiom, 121 bytes

f(m)==(r:=nrows(m);c:=ncols(m);for i in 1..r-1 repeat for j in 1..c-1 repeat if m(i,j)~=m(i+1,j+1)then return false;true)

m has to be a Matrix of some element that allow ~=; ungolf it

f m ==
  r := nrows(m)
  c := ncols(m)
  for i in 1..(r - 1) repeat
    for j in 1..(c - 1) repeat
      if m(i,j)~=m(i + 1,j + 1)     then return(false)
  true

Answer 15

R, 48 bytes

pryr::f(all(x[-1,-1]==x[-nrow(x),-ncol(x)])*2-1)

Try it online!

Answer 16

Retina, 148 bytes

m(1`\d+
$*#
1`#\n\d+\n
@
+`(#*)#@([^#\n]*(#*)\n)(.*)$
$1# $2$1@$4 #$3
@

+`##
# #
+(+s`^(\d+)\b(.*)^\1\b
$1$2#
s`.*^\d.*^\d.*
-1
)%`^[^- ]+ ?

\s+
1

Try it online!

An N×M input matrix

6 7 8 9 2 0
4 6 7 8 9 2
1 4 6 7 8 9
0 1 4 6 7 8

is first converted to an N×(N+M-1) matrix by aligning the diagonals this way:

# # # 6 7 8 9 2 0
# # 4 6 7 8 9 2 #
# 1 4 6 7 8 9 # #
0 1 4 6 7 8 # # #

and then the first column is repeatedly checked to contain a single unique number, and removed if this is so. The matrix is Toeplitz iff the output is blank.

Answer 17

MATL, 11 bytes

T&Xd"@Xz&=v

Try it online!

The straightforward "construct a Toeplitz matrix and check against it" method, that the top few answers use, somehow felt boring to me (and it looks like that would be 1 byte longer anyway). So I went for the "check each diagonal only contains one unique value" method.

T&Xd - Extract the diagonals of the input and create a new matrix with them as columns (padding with zeros as needed)

" - iterate through the columns of that

@Xz - push the iteration variable (the current column), and remove (padding) zeros from it

&= - broadcast equality check - this creates a matrix with all 1s (truthy) if all the remaining values are equal to one another, otherwise the matrix contains some 0s which is falsy

v - concatenate result values together, to create one final result vector which is either truthy (all 1s) or falsey (some 0s)

Answer 18

Japt, 9 bytes

I think this is right.

äÏÅeX¯JÃ×

Try it

äÏÅeX¯JÃ×     :Implicit input of 2D-array
ä             :Consecutive pairs
 Ï            :Reduced by
  Å           :  Slice the first element off the second array
   e          :  Check for equality with
    X         :    First array
     ¯J       :    Slice off the last element
       Ã      :End reduce
        ×     :Reduce by multiplication

Answer 19

Clojure, 94 bytes

#(if(=(+ %2 %3 -1)(count(set(for[Z[zipmap][i r](Z(range)%)[j v](Z(range)r)][(- i j)v]))))1 -1)