JavaScript program to check if matrix is ​​upper triangular

An upper triangular matrix is ​​a square matrix with the same number of rows and columns and all elements below the main diagonal from the first cell (located in the upper left corner) to The last cell (in the upper left corner, lower right corner) is zero. The upper triangle means that the elements present in the lower triangle will be zero. We will implement a proper code and the time and space complexities will be explained and discussed.

Example

Input1:
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 0, 0, 1]
]
Output1: Yes,

Explanation: We can see that the main diagonal contains elements 1, 5, 8 and 1, and all cells below the main diagonal have values ​​of zero.

Input2:
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 1, 0, 1]
]
Output1: No

Explanation: We can see that the main diagonal contains elements 1, 5, 8 and 1, and all cells below the main diagonal have non-zero values ​​because the second column of the last row contains non-zero value value.

method

We have seen the example above, now let’s look at the steps to implement the code:

First, we will create a function in which we pass the given matrix. We will traverse only the lower part of the main diagonal of the matrix, i.e. each cell (i,j) where j is less than i. If we find any cell with a non-zero value, we will return false, otherwise we will eventually return true.

Example

// function to traverse over the matrix
function check(mat){

   // getting total number of rows of matrix
   var rows = mat.length
   
   // traversing over the section present above the main diagonal
   for(var i = 0; i < rows; i++){
      for(var j = 0; j < i; j++){
         if(mat[i][j] != 0){
            return false;
         }
      }
   }
   return true;
}

// defining the matrix
var mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 0, 0, 1]
]
   
// given matrix
console.log("The given matrix is: ");
console.log(mat)
if(check(mat)){
   console.log("The given matrix is an upper triangular matrix");
}
else{
   console.log("The given matrix is not an upper triangular matrix");
}

// updating matrix
mat = [ [ 1, 2, 3, 4],
   [ 0, 5, 6, 7],
   [ 0, 0, 8, 9],
   [ 0, 1, 0, 1]
      ]
   
// given matrix
console.log("The given matrix is: ");
console.log(mat)
if(check(mat)){
   console.log("The given matrix is an upper triangular matrix");
}
else{
   console.log("The given matrix is not an upper triangular matrix");
}

Output

The given matrix is: 
[ [ 1, 2, 3, 4 ], [ 0, 5, 6, 7 ], [ 0, 0, 8, 9 ], [ 0, 0, 0, 1 ] ]
The given matrix is an upper triangular matrix
The given matrix is: 
[ [ 1, 2, 3, 4 ], [ 0, 5, 6, 7 ], [ 0, 0, 8, 9 ], [ 0, 1, 0, 1 ] ]
The given matrix is not an upper triangular matrix

Time and space complexity

The time complexity of the above code is O(N*N), where N is the number of rows of the given matrix. This is because we only iterate through the matrix once.

The space complexity of the above code is O(1) because we are not using any extra space.

in conclusion

In this tutorial, we implemented a JavaScript program to check whether a given matrix is ​​an upper triangular matrix. The upper triangle means that the elements present in the lower triangle will be zero. We iterate over the cells in the matrix where the number of columns is less than the number of rows, with time complexity O(N*N) and space complexity O(1).

The above is the detailed content of JavaScript program to check if matrix is ​​upper triangular. For more information, please follow other related articles on the PHP Chinese website!