Posted on by Kalkicode
Code Matrix

# Find if given matrix is Toeplitz or not

The problem involves determining whether a given matrix is a Toeplitz matrix or not. A Toeplitz matrix is a special type of matrix in which each diagonal from top-left to bottom-right has the same elements. In other words, the matrix has a constant value along each of its diagonals.

## Example

Consider the following matrix:

`````` 1  2  3  4  5
6  1  2  3  4
8  6  1  2  3
7  8  6  1  2
9  7  8  6  1``````

In this example, each diagonal from top-left to bottom-right contains the same elements, thus making it a Toeplitz matrix.

## Idea to Solve the Problem

The idea to solve this problem is to iterate through the matrix and for each element, check if the diagonal elements starting from that element are the same. If the diagonal elements are the same for all diagonals starting from each element in the first row and the first column, then the matrix is a Toeplitz matrix.

## Algorithm

1. Define a function `diagonal` that takes the matrix, start row, and start column as parameters.

2. Initialize a variable `element` with the value of the matrix element at `(start_row, start_col)`.

3. Loop through the diagonal elements:

• For each `(i, j)` element where `i = start_row + 1` and `j = start_col + 1`, compare the value of `matrix[i][j]` with `element`.
• If they are not equal, return 0, indicating that the diagonal is not the same.
4. Return 1, indicating that the diagonal is the same.

5. Define a function `is_toeplitz` that takes the matrix as a parameter.

6. Initialize a variable `result` to 1.

7. Loop through each column of the first row and check the diagonal using the `diagonal` function.

8. Loop through each row of the first column and check the diagonal using the `diagonal` function.

9. If `result` is 1, output "Toeplitz matrix," otherwise, output "Not a Toeplitz matrix."

## Pseudocode

``````diagonal(matrix, start_row, start_col):
element = matrix[start_row][start_col]
for i from start_row + 1 to ROW and j from start_col + 1 to COL:
if matrix[i][j] is not equal to element:
return 0
return 1

is_toeplitz(matrix):
result = 1
for i from 0 to COL:
result = diagonal(matrix, 0, i)
for i from 1 to ROW:
result = diagonal(matrix, i, 0)
if result is 1:
output "Toeplitz matrix"
else:
output "Not a Toeplitz matrix"

main:
matrix = ...  // Define the matrix
is_toeplitz(matrix)``````

## Code Solution

``````/*
C Program
+ Find if given matrix is Toeplitz or not
*/
#include<stdio.h>
#define ROW 5
#define COL 5

//Function which is check diagonal element values are similar or not
int diagonal(int matrix[ROW][COL],int start_row,int start_col)
{

int status  = 1;
int element = matrix[start_row][start_col];
for (int i = start_row+1,j=start_col+1; i < ROW && j<COL; ++i,++j)
{
if(matrix[i][j]!=element)
{
return 0;
}
}
return 1;
}
//Determine whether matrix is Toeplitz matrix or not
void is_toeplitz(int matrix[ROW][COL])
{

int result=1;

for (int i = 0; i < COL && result==1; ++i)
{
//check upper triangular
result = diagonal(matrix,0,i);
}
for (int i = 1; i < ROW && result==1; ++i)
{
//check lower triangular
result = diagonal(matrix,i,0);
}

if(result==1)
{
printf("Toeplitz matrix\n");
}
else
{
printf("Not a Toeplitz matrix\n");
}

}
int main(){

int arr[ROW][COL]={

{1,  2,  3,  4,  5},
{6,  1,  2,  3,  4},
{8,  6,  1,  2,  3},
{7,  8,  6,  1,  2},
{9,  7,  8,  6,  1}
};

is_toeplitz(arr);

return 0;
}```
```

#### Output

``Toeplitz matrix``
``````/*
C++ Program
Find if given matrix is Toeplitz or not
*/
#include<iostream>
#define ROW 5
#define COL 5
using namespace std;

class MyMatrix {
public:
int rows;
int cols;
MyMatrix() {
//Get matrix size
this->rows = ROW;
this->cols = COL;
}
//Function which is check diagonal element values are similar or not
bool diagonal(int matrix[][COL], int start_row, int start_col) {
int status = 1;
int element = matrix[start_row][start_col];
for (int i = start_row + 1, j = start_col + 1; i < this->rows && j < this->cols; ++i, ++j) {
if (matrix[i][j] != element) {
return false;
}
}
return true;
}
// Determine whether matrix is Toeplitz matrix or not
void is_toeplitz(int matrix[][COL]) {
bool result = true;
for (int i = 0; i < this->cols && result == true; ++i) {
//check upper triangular
result = this->diagonal(matrix, 0, i);
}
for (int i = 1; i < this->rows && result == true; ++i) {
//check lower triangular
result = this->diagonal(matrix, i, 0);
}
if (result == true) {
cout << "Toeplitz matrix\n";
} else {
cout << "Not a Toeplitz matrix\n";
}
}
};
int main() {
int matrix[][COL] = {
{
1,
2,
3,
4,
5
},
{
6,
1,
2,
3,
4
},
{
8,
6,
1,
2,
3
},
{
7,
8,
6,
1,
2
},
{
9,
7,
8,
6,
1
}
};
MyMatrix obj ;
obj.is_toeplitz(matrix);
return 0;
}```
```

#### Output

``Toeplitz matrix``
``````using System;

/*
C# Program
Find if given matrix is Toeplitz or not
*/

public class MyMatrix {
int rows;
int cols;
MyMatrix(int[,] matrix) {
//Get matrix size
this.rows = matrix.GetLength(0);
this.cols = matrix.GetLength(1);
}
//Function which is check diagonal element values are similar or not
public Boolean diagonal(int[,] matrix, int start_row, int start_col) {

int element = matrix[start_row,start_col];
for (int i = start_row + 1, j = start_col + 1; i < this.rows && j < this.cols; ++i, ++j) {
if (matrix[i,j] != element) {
return false;
}
}
return true;
}
// Determine whether matrix is Toeplitz matrix or not
public void is_toeplitz(int[,] matrix) {
Boolean result = true;
for (int i = 0; i < this.cols && result == true; ++i) {
//check upper triangular
result = diagonal(matrix, 0, i);
}
for (int i = 1; i < this.rows && result == true; ++i) {
//check lower triangular
result = diagonal(matrix, i, 0);
}
if (result == true) {
Console.Write("Toeplitz matrix\n");
} else {
Console.Write("Not a Toeplitz matrix\n");
}
}
public static void Main(String[] args) {
int[,]
//Define matrix element
matrix = {
{
1,
2,
3,
4,
5
},
{
6,
1,
2,
3,
4
},
{
8,
6,
1,
2,
3
},
{
7,
8,
6,
1,
2
},
{
9,
7,
8,
6,
1
}
};
MyMatrix obj = new MyMatrix(matrix);
obj.is_toeplitz(matrix);
}
}```
```

#### Output

``Toeplitz matrix``
``````<?php
/*
Php Program
Find if given matrix is Toeplitz or not
*/
class MyMatrix {
public \$rows;
public \$cols;

function __construct(\$matrix) {
//Get matrix size
\$this->rows = count(\$matrix);
\$this->cols = count(\$matrix[0]);
}
//Function which is check diagonal element values are similar or not

public 	function diagonal(\$matrix, \$start_row, \$start_col) {
\$element = \$matrix[\$start_row][\$start_col];
for (\$i = \$start_row + 1, \$j = \$start_col + 1; \$i < \$this->rows && \$j < \$this->cols; ++\$i, ++\$j) {
if (\$matrix[\$i][\$j] != \$element) {
return false;
}
}
return true;
}
// Determine whether matrix is Toeplitz matrix or not

public 	function is_toeplitz(\$matrix) {
\$result = true;
for (\$i = 0; \$i < \$this->cols && \$result == true; ++\$i) {
//check upper triangular
\$result = \$this->diagonal(\$matrix, 0, \$i);
}
for (\$i = 1; \$i < \$this->rows && \$result == true; ++\$i) {
//check lower triangular
\$result = \$this->diagonal(\$matrix, \$i, 0);
}
if (\$result == true) {
echo("Toeplitz matrix\n");
} else {
echo("Not a Toeplitz matrix\n");
}
}
}

function main() {
//Define matrix element
\$matrix = array(array(1, 2, 3, 4, 5), array(6, 1, 2, 3, 4), array(8, 6, 1, 2, 3), array(7, 8, 6, 1, 2), array(9, 7, 8, 6, 1));
\$obj = new MyMatrix(\$matrix);
\$obj->is_toeplitz(\$matrix);

}
main();```
```

#### Output

``Toeplitz matrix``
``````/*
Node Js Program
Find if given matrix is Toeplitz or not
*/
class MyMatrix {

constructor(matrix) {
//Get matrix size
this.rows = matrix.length;
this.cols = matrix[0].length;
}

//Function which is check diagonal element values are similar or not
diagonal(matrix, start_row, start_col) {
var element = matrix[start_row][start_col];
for (var i = start_row + 1, j = start_col + 1; i < this.rows && j < this.cols; ++i, ++j) {
if (matrix[i][j] != element) {
return false;
}
}

return true;
}

// Determine whether matrix is Toeplitz matrix or not
is_toeplitz(matrix) {
var result = true;
for (var i = 0; i < this.cols && result == true; ++i) {
//check upper triangular
result = this.diagonal(matrix, 0, i);
}

for (var i = 1; i < this.rows && result == true; ++i) {
//check lower triangular
result = this.diagonal(matrix, i, 0);
}

if (result == true) {
process.stdout.write("Toeplitz matrix\n");
} else {
process.stdout.write("Not a Toeplitz matrix\n");
}
}
}

function main(args) {
//Define matrix element
var matrix = [
[1, 2, 3, 4, 5],
[6, 1, 2, 3, 4],
[8, 6, 1, 2, 3],
[7, 8, 6, 1, 2],
[9, 7, 8, 6, 1]
];
var obj = new MyMatrix(matrix);
obj.is_toeplitz(matrix);
}

main();```
```

#### Output

``Toeplitz matrix``
``````#   Python 3 Program
#   Find if given matrix is Toeplitz or not
class MyMatrix :

def __init__(self, matrix) :
# Get matrix size
self.rows = len(matrix)
self.cols = len(matrix[0])

# Function which is check diagonal element values are similar or not
def diagonal(self, matrix, start_row, start_col) :
element = matrix[start_row][start_col]
i = start_row + 1
j = start_col + 1
while (i < self.rows and j < self.cols) :
if (matrix[i][j] != element) :
return False

i += 1
j += 1

return True

#  Determine whether matrix is Toeplitz matrix or not
def is_toeplitz(self, matrix) :
result = True
i = 0
while (i < self.cols and result == True) :
# check upper triangular
result = self.diagonal(matrix, 0, i)
i += 1

i = 1
while (i < self.rows and result == True) :
# check lower triangular
result = self.diagonal(matrix, i, 0)
i += 1

if (result == True) :
print("Toeplitz matrix\n", end = "")
else :
print("Not a Toeplitz matrix\n", end = "")

def main() :
matrix = [
[1, 2, 3, 4, 5],
[6, 1, 2, 3, 4],
[8, 6, 1, 2, 3],
[7, 8, 6, 1, 2],
[9, 7, 8, 6, 1]
]
obj = MyMatrix(matrix)
obj.is_toeplitz(matrix)

if __name__ == "__main__":
main()```
```

#### Output

``Toeplitz matrix``
``````# Ruby Program
# Find if given matrix is Toeplitz or not
class MyMatrix
# Define the accessor and reader of class MyMatrix
attr_accessor :rows, :cols
def initialize(matrix)
# Get matrix size
self.rows = matrix.length
self.cols = matrix[0].length
end
# Function which is check diagonal element values are similar or not
def diagonal(matrix, start_row, start_col)
element = matrix[start_row][start_col]
i = start_row + 1
j = start_col + 1
while (i < self.rows && j < self.cols)
if (matrix[i][j] != element)
return false
end
i += 1
j += 1
end
return true
end
#  Determine whether matrix is Toeplitz matrix or not
def is_toeplitz(matrix)
result = true
i = 0
while (i < self.cols && result == true)
# check upper triangular
result = self.diagonal(matrix, 0, i)
i += 1
end
i = 1
while (i < self.rows && result == true)
# check lower triangular
result = self.diagonal(matrix, i, 0)
i += 1
end
if (result == true)
print("Toeplitz matrix\n")
else
print("Not a Toeplitz matrix\n")
end
end
end
def main()
matrix = [
[1, 2, 3, 4, 5],
[6, 1, 2, 3, 4],
[8, 6, 1, 2, 3],
[7, 8, 6, 1, 2],
[9, 7, 8, 6, 1]
]
obj = MyMatrix.new(matrix)
obj.is_toeplitz(matrix)
end

main()```
```

#### Output

``````Toeplitz matrix
``````
``````/*
Scala Program
Find if given matrix is Toeplitz or not
*/
class MyMatrix(var rows: Int,
var cols: Int) {

def this(matrix: Array[Array[Int]]) {
//Get matrix size
this(matrix.length,matrix(0).length);
}
//Function which is check diagonal element values are similar or not
def diagonal(matrix: Array[Array[Int]], start_row: Int, start_col: Int): Boolean = {
val element: Int = matrix(start_row)(start_col);
var i: Int = start_row + 1;
var j: Int = start_col + 1;
while (i < this.rows && j < this.cols) {
if (matrix(i)(j) != element) {
return false;
}
i += 1;
j += 1;
}
return true;
}
// Determine whether matrix is Toeplitz matrix or not
def is_toeplitz(matrix: Array[Array[Int]]): Unit = {
var result: Boolean = true;
var i: Int = 0;
while (i < this.cols && result == true) {
//check upper triangular
result = this.diagonal(matrix, 0, i);
i += 1;
}
i = 1;
while (i < this.rows && result == true) {
//check lower triangular
result = this.diagonal(matrix, i, 0);
i += 1;
}
if (result == true) {
print("Toeplitz matrix\n");
} else {
print("Not a Toeplitz matrix\n");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val matrix: Array[Array[Int]] = Array(
Array(1, 2, 3, 4, 5),
Array(6, 1, 2, 3, 4),
Array(8, 6, 1, 2, 3),
Array(7, 8, 6, 1, 2),
Array(9, 7, 8, 6, 1));
val obj: MyMatrix = new MyMatrix(matrix);
obj.is_toeplitz(matrix);
}
}```
```

#### Output

``Toeplitz matrix``
``````/*
Swift Program
Find if given matrix is Toeplitz or not
*/
class MyMatrix {
var rows: Int;
var cols: Int;
init(_ matrix: [
[Int]
]) {
//Get matrix size
self.rows = matrix.count;
self.cols = matrix[0].count;
}
//Function which is check diagonal element values are similar or not
func diagonal(_ matrix: [
[Int]
], _ start_row: Int, _ start_col: Int) -> Bool {
let element: Int = matrix[start_row][start_col];
var i: Int = start_row + 1;
var j: Int = start_col + 1;
while (i < self.rows && j < self.cols) {
if (matrix[i][j] != element) {
return false;
}
i += 1;
j += 1;
}
return true;
}
// Determine whether matrix is Toeplitz matrix or not
func is_toeplitz(_ matrix: [
[Int]
]) {
var result: Bool = true;
var i: Int = 0;
while (i < self.cols && result == true) {
//check upper triangular
result = self.diagonal(matrix, 0, i);
i += 1;
}
i = 1;
while (i < self.rows && result == true) {
//check lower triangular
result = self.diagonal(matrix, i, 0);
i += 1;
}
if (result == true) {
print("Toeplitz matrix\n", terminator: "");
} else {
print("Not a Toeplitz matrix\n", terminator: "");
}
}
}
func main() {
let matrix: [
[Int]
] = [
[1, 2, 3, 4, 5],
[6, 1, 2, 3, 4],
[8, 6, 1, 2, 3],
[7, 8, 6, 1, 2],
[9, 7, 8, 6, 1]
];
let obj: MyMatrix = MyMatrix(matrix);
obj.is_toeplitz(matrix);
}
main();```
```

#### Output

``Toeplitz matrix``
``````/*
Java Program
Find if given matrix is Toeplitz or not
*/
public class MyMatrix {

public int rows;
public int cols;
public MyMatrix(int [][]matrix)
{
//Get matrix size
this.rows = matrix.length;
this.cols = matrix[0].length;

}
//Function which is check diagonal element values are similar or not
public boolean diagonal(int [][]matrix,int start_row,int start_col)
{
int element = matrix[start_row][start_col];
for (int i = start_row+1,j=start_col+1; i < this.rows && j<this.cols; ++i,++j)
{
if(matrix[i][j]!=element)
{
return false;
}
}
return true;
}
// Determine whether matrix is Toeplitz matrix or not
public void is_toeplitz(int [][]matrix)
{

boolean result=true;

for (int i = 0; i < this.cols && result==true; ++i)
{
//check upper triangular
result=diagonal(matrix,0,i);
}
for (int i = 1; i < this.rows && result==true; ++i)
{
//check lower triangular
result=diagonal(matrix,i,0);
}

if(result==true)
{
System.out.print("Toeplitz matrix\n");
}
else
{
System.out.print("Not a Toeplitz matrix\n");
}

}

public static void main(String[] args)
{
//Define matrix element
int [][]matrix ={

{1,  2,  3,  4,  5},
{6,  1,  2,  3,  4},
{8,  6,  1,  2,  3},
{7,  8,  6,  1,  2},
{9,  7,  8,  6,  1}
};
MyMatrix obj = new MyMatrix(matrix);
obj.is_toeplitz(matrix);
}
}```
```

#### Output

``Toeplitz matrix``

## Output Explanation

The provided C code implements the above algorithm to determine whether a given matrix is a Toeplitz matrix. It iterates through the matrix and checks the diagonal elements starting from each element in the first row and the first column. If all diagonals have the same elements, it outputs "Toeplitz matrix." Otherwise, it outputs "Not a Toeplitz matrix."

## Time Complexity

The time complexity of the algorithm is O(ROW * COL), where ROW is the number of rows and COL is the number of columns in the matrix. This is because the algorithm iterates through each element of the matrix and checks the diagonal elements for each element.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post