Check if a Matrix Is Upper Triangular: Code and Complexity

A square matrix is upper triangular if every element below the main diagonal equals zero, and verifying that condition takes a nested loop that inspects at most n(n-1)/2 positions.

What Is an Upper Triangular Matrix?

The triangular matrix family has two members. An upper triangular matrix has zeros in every position where the row index is strictly greater than the column index. A lower triangular matrix has zeros in every position where the column index is strictly greater than the row index.

More precisely, for an n×n matrix A:

• A is upper triangular when A[i][j] == 0 for all i > j.
• A is lower triangular when A[i][j] == 0 for all i < j.

A concrete 3×3 upper triangular example:

| 4  3  2 |
| 0  7  1 |
| 0  0  5 |

Every position below the main diagonal (bottom-left triangle) is zero. Elements on the diagonal and above it can be any value.

A 3×3 matrix that is NOT upper triangular:

| 4  3  2 |
| 0  7  1 |
| 0  6  5 |    ← position [2][1] = 6, non-zero below the diagonal

The diagonal itself is included in the upper triangular region. That means a diagonal matrix, where every off-diagonal element is zero, satisfies the upper triangular condition as a special case.

The Condition and Algorithm

The check translates directly into code. Iterate over every position strictly below the main diagonal. If any element there is non-zero, the matrix fails the check. If the loop completes without finding a non-zero element, the matrix is upper triangular.

In pseudocode (0-indexed):

for i from 1 to n-1:          # rows that have a below-diagonal region
    for j from 0 to i-1:      # columns to the left of the diagonal
        if mat[i][j] != 0:
            return NOT_UPPER_TRIANGULAR
return UPPER_TRIANGULAR

The outer loop starts at row 1, not row 0. Row 0 has no positions below the diagonal, so skipping it is correct and not an off-by-one error.

The inner loop runs from column 0 up to, but not including, the diagonal column i. For a 3×3 matrix, this visits positions (1,0), (2,0), and (2,1), covering exactly the three cells in the lower-triangular region.

Short-circuiting matters for matrices that fail early. A matrix with a non-zero element at position (1,0) exits the check after one comparison rather than scanning all n(n-1)/2 positions.

Code in C, Python, and Java

C

#include <stdio.h>
#define MAX 10

int isUpperTriangular(int mat[][MAX], int n) {
    int i, j;
    for (i = 1; i < n; i++) {
        for (j = 0; j < i; j++) {
            if (mat[i][j] != 0)
                return 0;
        }
    }
    return 1;
}

int main() {
    int n, i, j;
    int mat[MAX][MAX];

    printf("Enter the order of the matrix: ");
    scanf("%d", &n);

    printf("Enter the matrix elements row by row:\n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &mat[i][j]);

    if (isUpperTriangular(mat, n))
        printf("Upper Triangular Matrix\n");
    else
        printf("Not an Upper Triangular Matrix\n");

    return 0;
}

Sample run with the 3×3 upper triangular matrix shown above:

Enter the order of the matrix: 3
Enter the matrix elements row by row:
4 3 2
0 7 1
0 0 5
Upper Triangular Matrix

Python

def is_upper_triangular(mat):
    n = len(mat)
    for i in range(1, n):
        for j in range(i):
            if mat[i][j] != 0:
                return False
    return True

n = int(input("Enter order: "))
mat = []
for _ in range(n):
    row = list(map(int, input().split()))
    mat.append(row)

if is_upper_triangular(mat):
    print("Upper Triangular Matrix")
else:
    print("Not an Upper Triangular Matrix")

Sample run with the non-upper-triangular matrix (element 6 at position [2][1]):

Enter order: 3
4 3 2
0 7 1
0 6 5
Not an Upper Triangular Matrix

Java

import java.util.Scanner;

public class UpperTriangular {

    static boolean isUpperTriangular(int[][] mat, int n) {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (mat[i][j] != 0)
                    return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter order: ");
        int n = sc.nextInt();
        int[][] mat = new int[n][n];
        System.out.println("Enter matrix elements row by row:");
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                mat[i][j] = sc.nextInt();

        if (isUpperTriangular(mat, n))
            System.out.println("Upper Triangular Matrix");
        else
            System.out.println("Not an Upper Triangular Matrix");
    }
}

All three implementations follow the same logic: iterate below the diagonal, short-circuit on the first non-zero value, return true if the loop completes without finding one.

Time and Space Complexity

Time Complexity

O(n²) in the worst case. When the matrix is upper triangular, the algorithm visits every position below the diagonal. The count of those positions is n(n-1)/2, which is O(n²). When the matrix is not upper triangular and the first violation appears at position (1,0), the function exits after a single comparison (best case O(1)). Average case depends on where the first non-zero sits.

The O(n²) class places this check in the same group as bubble sort and selection sort: workable for matrices of moderate size, but worth noting if this check runs inside a broader O(n²) or O(n³) algorithm.

Space Complexity

O(1). No additional data structure is allocated. The function uses a fixed number of loop counters regardless of n. For a detailed breakdown of how to classify auxiliary space in similar programs, see Space Complexity of Algorithms with Worked Examples.

Upper vs. Lower Triangular and Placement Context

The two checks differ only in which region gets scanned:

Check	Condition	Region inspected
Upper triangular	mat[i][j] == 0 for i > j	Below the diagonal
Lower triangular	mat[i][j] == 0 for i < j	Above the diagonal

A matrix that satisfies both conditions simultaneously is a diagonal matrix, meaning every off-diagonal element is zero.

In placement coding rounds, this question tests whether you can translate a geometric property of a matrix into correct loop bounds. The common mistakes are:

• Starting the outer loop at row 0 (harmless but unnecessary — row 0 has no below-diagonal elements).
• Using j <= i instead of j < i in the inner loop, which incorrectly includes the diagonal.
• Scanning the full n×n matrix instead of only the lower-triangular region, which wastes comparisons but still gives the right answer.

Interviewers at service-tier companies occasionally follow up with the lower-triangular variant in the same session. The code change is one character: i > j becomes i < j in the condition. For the symmetric-pair variant of array problems that also use nested loops to compare two positions, see Find All Symmetric Pairs in an Array.

When working with matrices in production code rather than placement interviews, numpy.triu extracts the upper triangular portion of a matrix directly. Placement rounds always expect the from-scratch implementation.

The O(n²) scan pattern in this check (iterate below the diagonal, short-circuit on the first non-zero) reappears in many matrix operations inside scientific computing and machine learning libraries. If that connection interests you, TinkerLLM at ₹299 lets you run language models that depend on those same matrix foundations without setting up a research environment from scratch.