Check if matrix is upper triangular

The problem is about the checking whether a given matrix is upper triangular or not. An upper triangular matrix is a special type of square matrix where all the elements below the main diagonal (elements with row index greater than column index) are zero.

Problem Statement and Example

Given a matrix, we want to determine if it's an upper triangular matrix. For example, consider the following matrix:

1  2  3  4
0  1  2  3
0  0  1  2
0  0  0  5

In this example, the matrix is indeed upper triangular because all the elements below the main diagonal are zeros.

Idea to Solve

To solve this problem, we need to iterate through each element of the matrix and check if it satisfies the conditions of being an upper triangular matrix. Specifically, for each element at position (i, j), we need to ensure that all elements with row indices greater than i (i.e., the elements below the current row) and column indices less than j (i.e., the elements to the left of the current column) are zero.

Pseudocode

function isUpperTriangular(matrix)
    for i = 0 to number_of_rows(matrix) - 1
        for j = 0 to i
            if matrix[i][j] != 0
                return false
    return true

Algorithm Explanation

1. Loop through each row of the matrix using the variable i.
2. For each row, loop through the columns from 0 to i using the variable j.
3. Check if the element at position (i, j) is non-zero. If it's not zero, the matrix can't be upper triangular, so return false.
4. If all elements below the main diagonal are zero, the matrix is upper triangular, so return true.

Code Solution

• C
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

/*
  C Program 
+ Check if matrix is upper triangular
*/
#include<stdio.h>
//Size of matrix
#define ROW 4
#define COL 4

//Display the element of given 2d matrix
void show_data(int matrix[][COL]) {

  
  for (int i = 0; i < ROW; ++i) {

    for (int j = 0; j < COL; ++j) {

      printf("%4d", matrix[i][j]);
    }

    printf("\n");
  }

  printf("\n");
}
//Check if given matrix is upper triangular or not
void upper_triangular(int matrix[ROW][COL])
{
  int status=1;
 
  for (int i = 0; i < COL && status==1; ++i)
  {
    for (int j = 0; j < i && status==1; ++j)
    {
      if(matrix[i][j] != 0)
      {
        //When matrix is not upper triangular
        status=0;
      }
    }
    
  }
  if(status==1)
  {
    printf("  Yes\n");
  }
  else
  {
    printf("  NO\n");
  }
 
}
int main(){

  int matrix[ROW][COL]=  { 
    { 1, 2, 3, 4 }, 
    { 0, 1, 2, 3 }, 
    { 0, 0, 1, 2 },
    { 0, 0, 0, 5 }  }; 
  show_data(matrix);
  upper_triangular(matrix);

  return 0;
}

   1   2   3   4
   0   1   2   3
   0   0   1   2
   0   0   0   5

  Yes

/*
  C++ Program
  Check if matrix is upper triangular
*/
#include<iostream>
#define ROW 4
#define COL 4
using namespace std;


class MyMatrix {
	public:

		//Display the element of given 2d matrix
		void show_data(int matrix[][COL], int row, int col) {
			for (int i = 0; i < row; ++i) {
				for (int j = 0; j < col; ++j) {
					cout << " " << matrix[i][j];
				}
				cout << "\n";
			}
			cout << "\n";
		}
	//Check if given matrix is upper triangular or not
	void upper_triangular(int matrix[][COL], int row, int col) {
		int status = 1;
		for (int i = 0; i < col && status == 1; ++i) {
			for (int j = 0; j < i && status == 1; ++j) {
				if (matrix[i][j] != 0) {
					//When matrix is not upper triangular
					status = 0;
				}
			}
		}
		if (status == 1) {
			cout << " Yes\n";
		} else {
			cout << " NO\n";
		}
	}
};
int main() {
	MyMatrix obj ;
	int matrix[][COL] = {
		{
			1,
			2,
			3,
			4
		},
		{
			0,
			1,
			2,
			3
		},
		{
			0,
			0,
			1,
			2
		},
		{
			0,
			0,
			0,
			5
		}
	};

	obj.show_data(matrix, ROW, COL);
	obj.upper_triangular(matrix, ROW, COL);
	return 0;
}

 1 2 3 4
 0 1 2 3
 0 0 1 2
 0 0 0 5

 Yes

/*
  Java Program
  Check if matrix is upper triangular
*/
public class MyMatrix {


  //Display the element of given 2d matrix
  public void show_data(int [][]matrix, int row,int col) {

    
    for (int i = 0; i < row; ++i) {

      for (int j = 0; j < col; ++j) {

        System.out.print("  "+ matrix[i][j]);
      }

      System.out.print("\n");
    }

    System.out.print("\n");
  }
  //Check if given matrix is upper triangular or not
  public void upper_triangular(int [][]matrix, int row,int col)
  {
    int status=1;
   
    for (int i = 0; i < col && status==1; ++i)
    {
      for (int j = 0; j < i && status==1; ++j)
      {
        if(matrix[i][j] != 0)
        {
          //When matrix is not upper triangular
          status=0;
        }
      }
      
    }
    if(status==1)
    {
      System.out.print("  Yes\n");
    }
    else
    {
      System.out.print("  NO\n");
    }
   
  }

  public static void main(String[] args) 
  {
  

    MyMatrix obj = new MyMatrix();
    int [][]matrix =  { 
      { 1, 2, 3, 4 }, 
      { 0, 1, 2, 3 }, 
      { 0, 0, 1, 2 },
      { 0, 0, 0, 5 }  
    }; 
    //This is size of matrix
    int row = matrix.length;
    int col = matrix[0].length; 

    obj.show_data(matrix,row,col);
    obj.upper_triangular(matrix,row,col);

  }
}

 1 2 3 4
 0 1 2 3
 0 0 1 2
 0 0 0 5

 Yes

/*
  C# Program
  Check if matrix is upper triangular
*/
using System;
public class MyMatrix {
	//Display the element of given 2d matrix
	public void show_data(int[,] matrix, int row, int col) {
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < col; ++j) {
				Console.Write(" " + matrix[i,j]);
			}
			Console.Write("\n");
		}
		Console.Write("\n");
	}
	//Check if given matrix is upper triangular or not
	public void upper_triangular(int[,] matrix, int row, int col) {
		int status = 1;
		for (int i = 0; i < col && status == 1; ++i) {
			for (int j = 0; j < i && status == 1; ++j) {
				if (matrix[i,j] != 0) {
					//When matrix is not upper triangular
					status = 0;
				}
			}
		}
		if (status == 1) {
			Console.Write(" Yes\n");
		} else {
			Console.Write(" NO\n");
		}
	}
	public static void Main(String[] args) {
		MyMatrix obj = new MyMatrix();
		int[,] matrix = {
			{
				1,
				2,
				3,
				4
			},
			{
				0,
				1,
				2,
				3
			},
			{
				0,
				0,
				1,
				2
			},
			{
				0,
				0,
				0,
				5
			}
		};
		//This is size of matrix
		int row = matrix.GetLength(0);
		int col = matrix.GetLength(1);
		obj.show_data(matrix, row, col);
		obj.upper_triangular(matrix, row, col);
	}
}

 1 2 3 4
 0 1 2 3
 0 0 1 2
 0 0 0 5

 Yes

<?php
/*
  Php Program
  Check if matrix is upper triangular
*/
class MyMatrix {
	//Display the element of given 2d matrix

	public 	function show_data($matrix, $row, $col) {
		for ($i = 0; $i < $row; ++$i) {
			for ($j = 0; $j < $col; ++$j) {
				echo(" ". $matrix[$i][$j]);
			}
			echo("\n");
		}
		echo("\n");
	}
	//Check if given matrix is upper triangular or not

	public 	function upper_triangular($matrix, $row, $col) {
		$status = 1;
		for ($i = 0; $i < $col && $status == 1; ++$i) {
			for ($j = 0; $j < $i && $status == 1; ++$j) {
				if ($matrix[$i][$j] != 0) {
					//When matrix is not upper triangular
					$status = 0;
				}
			}
		}
		if ($status == 1) {
			echo(" Yes\n");
		} else {
			echo(" NO\n");
		}
	}
};

function main() {
	$obj = new MyMatrix();
	$matrix = array(
      array(1, 2, 3, 4), 
      array(0, 1, 2, 3), 
      array(0, 0, 1, 2), 
      array(0, 0, 0, 5)
    );
	//This is size of matrix
	$row = count($matrix);
	$col = count($matrix[0]);
	$obj->show_data($matrix, $row, $col);
	$obj->upper_triangular($matrix, $row, $col);

}
main();

 1 2 3 4
 0 1 2 3
 0 0 1 2
 0 0 0 5

 Yes

/*
  Node Js Program
  Check if matrix is upper triangular
*/
class MyMatrix {
	//Display the element of given 2d matrix
	show_data(matrix, row, col) {
		for (var i = 0; i < row; ++i) {
			for (var j = 0; j < col; ++j) {
				process.stdout.write(" " + matrix[i][j]);
			}

			process.stdout.write("\n");
		}

		process.stdout.write("\n");
	}

	//Check if given matrix is upper triangular or not
	upper_triangular(matrix, row, col) {
		var status = 1;
		for (var i = 0; i < col && status == 1; ++i) {
			for (var j = 0; j < i && status == 1; ++j) {
				if (matrix[i][j] != 0) {
					//When matrix is not upper triangular
					status = 0;
				}
			}
		}

		if (status == 1) {
			process.stdout.write(" Yes\n");
		} else {
			process.stdout.write(" NO\n");
		}
	}
}

function main(args) {
	var obj = new MyMatrix();
	var matrix = [
		[1, 2, 3, 4],
		[0, 1, 2, 3],
		[0, 0, 1, 2],
		[0, 0, 0, 5]
	];
	//This is size of matrix
	var row = matrix.length;
	var col = matrix[0].length;
	obj.show_data(matrix, row, col);
	obj.upper_triangular(matrix, row, col);
}

main();

 1 2 3 4
 0 1 2 3
 0 0 1 2
 0 0 0 5

 Yes

#  Python 3 Program
#  Check if matrix is upper triangular
class MyMatrix :
	# Display the element of given 2d matrix
	def show_data(self, matrix, row, col) :
		i = 0
		while (i < row) :
			j = 0
			while (j < col) :
				print(" ", matrix[i][j], end = "")
				j += 1
			
			print("\n", end = "")
			i += 1
		
		print("\n", end = "")
	
	# Check if given matrix is upper triangular or not
	def upper_triangular(self, matrix, row, col) :
		status = 1
		i = 0
		while (i < col and status == 1) :
			j = 0
			while (j < i and status == 1) :
				if (matrix[i][j] != 0) :
					# When matrix is not upper triangular
					status = 0
				
				j += 1
			
			i += 1
		
		if (status == 1) :
			print(" Yes\n", end = "")
		else :
			print(" NO\n", end = "")
		
	

def main() :
	obj = MyMatrix()
	matrix = [
		[1, 2, 3, 4],
		[0, 1, 2, 3],
		[0, 0, 1, 2],
		[0, 0, 0, 5]
	]
	row = len(matrix)
	col = len(matrix[0])
	obj.show_data(matrix, row, col)
	obj.upper_triangular(matrix, row, col)


if __name__ == "__main__":
	main()

  1  2  3  4
  0  1  2  3
  0  0  1  2
  0  0  0  5

 Yes

# Ruby Program
# Check if matrix is upper triangular
class MyMatrix 
	# Display the element of given 2d matrix
	def show_data(matrix, row, col) 
		i = 0
		while (i < row) 
			j = 0
			while (j < col) 
				print(" ", matrix[i][j])
				j += 1
			end
			print("\n")
			i += 1
		end
		print("\n")
	end
	# Check if given matrix is upper triangular or not
	def upper_triangular(matrix, row, col) 
		status = 1
		i = 0
		while (i < col && status == 1) 
			j = 0
			while (j < i && status == 1) 
				if (matrix[i][j] != 0) 
					# When matrix is not upper triangular
					status = 0
				end
				j += 1
			end
			i += 1
		end
		if (status == 1) 
			print(" Yes\n")
		else 
			print(" NO\n")
		end
	end
end
def main() 
	obj = MyMatrix.new()
	matrix = [
		[1, 2, 3, 4],
		[0, 1, 2, 3],
		[0, 0, 1, 2],
		[0, 0, 0, 5]
	]
	row = matrix.length
	col = matrix[0].length
	obj.show_data(matrix, row, col)
	obj.upper_triangular(matrix, row, col)
end
main()

 1 2 3 4
 0 1 2 3
 0 0 1 2
 0 0 0 5

 Yes

/*
  Scala Program
  Check if matrix is upper triangular
*/
class MyMatrix {
	//Display the element of given 2d matrix
	def show_data(matrix: Array[Array[Int]], row: Int, col: Int): Unit = {
		var i: Int = 0;
		while (i < row) {
			var j: Int = 0;
			while (j < col) {
				print(" " + matrix(i)(j));
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	//Check if given matrix is upper triangular or not
	def upper_triangular(matrix: Array[Array[Int]], row: Int, col: Int): Unit = {
		var status: Int = 1;
		var i: Int = 0;
		while (i < col && status == 1) {
			var j: Int = 0;
			while (j < i && status == 1) {
				if (matrix(i)(j) != 0) {
					//When matrix is not upper triangular
					status = 0;
				}
				j += 1;
			}
			i += 1;
		}
		if (status == 1) {
			print(" Yes\n");
		} else {
			print(" NO\n");
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyMatrix = new MyMatrix();
		val matrix: Array[Array[Int]] = Array(
			Array(1, 2, 3, 4),
			Array(0, 1, 2, 3),
			Array(0, 0, 1, 2),
			Array(0, 0, 0, 5));
		val row: Int = matrix.length;
		val col: Int = matrix(0).length;
		obj.show_data(matrix, row, col);
		obj.upper_triangular(matrix, row, col);
	}
}

 1 2 3 4
 0 1 2 3
 0 0 1 2
 0 0 0 5

 Yes

/*
  Swift Program
  Check if matrix is upper triangular
*/
class MyMatrix {
	//Display the element of given 2d matrix
	func show_data(_ matrix: [
		[Int]
	], _ row: Int, _ col: Int) {
		var i: Int = 0;
		while (i < row) {
			var j: Int = 0;
			while (j < col) {
				print(" ", matrix[i][j], terminator: "");
				j += 1;
			}
			print("\n", terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	//Check if given matrix is upper triangular or not
	func upper_triangular(_ matrix: [
		[Int]
	], _ row: Int, _ col: Int) {
		var status: Int = 1;
		var i: Int = 0;
		while (i < col && status == 1) {
			var j: Int = 0;
			while (j < i && status == 1) {
				if (matrix[i][j] != 0) {
					//When matrix is not upper triangular
					status = 0;
				}
				j += 1;
			}
			i += 1;
		}
		if (status == 1) {
			print(" Yes\n", terminator: "");
		} else {
			print(" NO\n", terminator: "");
		}
	}
}
func main() {
	let obj: MyMatrix = MyMatrix();
	let matrix: [
		[Int]
	] = [
		[1, 2, 3, 4],
		[0, 1, 2, 3],
		[0, 0, 1, 2],
		[0, 0, 0, 5]
	];
	let row: Int = matrix.count;
	let col: Int = matrix[0].count;
	obj.show_data(matrix, row, col);
	obj.upper_triangular(matrix, row, col);
}
main();

  1  2  3  4
  0  1  2  3
  0  0  1  2
  0  0  0  5

 Yes

Time Complexity

The time complexity of this algorithm is O(n^2), where 'n' is the number of rows (or columns) in the matrix. This is because we need to iterate through each element of the matrix once and perform a constant amount of work for each element.