## Thursday, August 4, 2016

### Find if given matrix is Toeplitz or not - GeeksforGeeks

Find if given matrix is Toeplitz or not - GeeksforGeeks
Given a square matrix, find if it's a Toeplitz matrix or not. A Toeplitz (or diagonal-constant) matrix is a matrix in which each descending diagonal from left to right is constant, i.e., all elements in a diagonal are same.
In general, any n×n matrix mat[][] is a Toeplitz matrix if every cell mat[i][j] is same as mat[i-1][j-1], mat[i+1][j+1], mat[i-2][j-2], mat[i+2][j+2], .. for every cell mat[i][j] and all the valid cells mat[i+k][j+k] or mat[i-k][j-k]
`// Function to check if all elements present in`
`// descending diagonal starting from position`
`// (i, j) in the matrix are all same or not`
`bool` `checkDiagonal(``int` `mat[N][M], ``int` `i, ``int` `j)`
`{`
`    ``int` `res = mat[i][j];`
`    ``while` `(++i < N && ++j < M)`
`    ``{`
`        ``// mismatch found`
`        ``if` `(mat[i][j] != res)`
`            ``return` `false``;`
`    ``}`
`    ``// we only reach here when all elements`
`    ``// in given diagonal are same`
`    ``return` `true``;`
`}`
`// Function to check whether given matrix is a`
`// Toeplitz matrix or not`
`bool` `isToepliz(``int` `mat[N][M])`
`{`
`    ``// do for each element in first row`
`    ``for` `(``int` `i = 0; i < M; i++)`
`    ``{`
`        ``// check descending diagonal starting from`
`        ``// position (0, j) in the matrix`
`        ``if` `(!checkDiagonal(mat, 0, i))`
`            ``return` `false``;`
`    ``}`
`    ``// do for each element in first column`
`    ``for` `(``int` `i = 1; i < N; i++)`
`    ``{`
`        ``// check descending diagonal starting from`
`        ``// position (i, 0) in the matrix`
`        ``if` `(!checkDiagonal(mat, i, 0))`
`            ``return` `false``;`
`    ``}`
`    ``// we only reach here when each descending`
`    ``// diagonal from left to right is same`
`    ``return` `true``;`
`}`