FOR FREE CONTENT

Finding Upper Triangular Matrix

Back to Programming

Description

A matrix is said to be an upper triangular matrix if the elements under the principal diagonal is 0. The matrix should be a square matrix.

 

For example

 

This is an example of an upper triangular matrix as all the elements below the principal diagonal is 0.

For any matrix A, if all elements Aij = 0 for all i>j.

Now, let the matrix be: 

 

Here we have used a 3×3 matrix. So, the index values are:

 

Now, the indexes where the value of is greater than j are:

 

So, the values of these indices in the original matrix A will be set to 0. The target elements of the original matrix are:

 

These elements will be replaced by 0 and we will get the upper triangular matrix as:

Algorithm

INPUT: A matrix 
OUTPUT: The upper triangular matrix

PROCESS:
Step 1: [Taking the inputs]
	Read m, n [the number of rows and columns of the matrix]
	For i=0 to m-1 repeat
		For j=0 to n-1 repeat 
			Read a[i][j]
		[End of ‘for’ loop]
	[End of ‘for’ loop]
Step 2: [Finding the upper triangular matrix]
	for i = 0 to m-1 repeat
        		for j = 0 to n-1 repeat
        			if i>j then
        				print "0 "
        			else
        				print a[i][j]
			[End of ‘if’]
		[End of ‘for’ loop]
		Move to the next line
	[End of ‘for’ loop]
Step 3: Stop.

Code

TIME COMPLEXITY:

                 for (i = 0; i < m; i++)------------- O(m)

                 {        for (j = 0; j < n; j++)----- O(n)

                                {             if(i>j)-------------- O(c1)

                                                                printf("0 ");

                                                else--------------- O(c2)

                                                                printf("%d ",a[i][j]);

                                }

                                printf("\n");--------------- O(1)

                }

c1 and c2 is constant. Therefore, the time complexity is O(m*n). if the number of rows and columns of the matrix is equal, then the time complexity of the matrix is O(n2).