Data Modelling & AI Data Structure & Algorithm

Efficient method to store a Lower Triangular Matrix using Column-major mapping

23 June 2025

0

Given a lower triangular matrix Mat[][], the task is to store the matrix using column-major mapping.

Lower Triangular Matrix: A Lower Triangular Matrix is a square matrix in which the lower triangular part of a matrix consists of non-zero elements and the upper triangular part consists of 0s. The Lower Triangular Matrix for a 2D matrix Mat[][] is mathematically defined as:

If i < j, set Mat[i][j] = 0.
If i >= j, set Mat[i][j] > 0.

Illustration:

Below is a 5×5 lower triangular matrix. In general, such matrices can be stored in a 2D array, but when it comes to matrices of large size, it is not a good choice because of its high memory consumption due to the storage of unwanted 0s.
Such a matrix can be implemented in an optimized manner.

The efficient way to store the lower triangular matrix of size N:

Count of non-zero elements = 1 + 2 + 3 + … + N = N * (N + 1) /2.
Count of 0s = N²– (N * (N + 1) /2 = (N * (N – 1)/2.

Now let see how to represent lower triangular matrices in the program. Notice that storing 0s must be avoided to reduce memory consumption. As calculated, for storing non-zero elements, N*(N + 1)/2 space is needed. Taking the above example, N = 5. Array of size 5 * (5 + 1)/2 = 15 is required to store the non-zero elements.

Now, elements of the 2D matrix can be stored in a 1D array, column by column, as shown below:

Array to store Lower Triangular Elements

Apart from storing the elements in an array, a procedure for extracting the element corresponding to the row and column number is also required. Using Column-Major-Mapping for storing a lower triangular matrix, the element at index Mat[i][j] can be represented as:

Index of Mat[i][j] matrix in the array A[] = [n*(j-1)-(((j-2)*(j-1))/2)+ (i-j))]

Below is the implementation of the above article:

C++

// C++ program for the above approach 
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
 
// Dimensions of the matrix 
const int N = 5;
 
// Structure of a memory 
// efficient matrix
struct Matrix {
    int* A;
    int size;
};
 
// Function to set the 
// values in the Matrix 
void Set(struct Matrix* m, int i, 
         int j, int x)
{
    if (i >= j)
        m->A[((m->size)*(j-1)-(((j-2)
              *(j-1))/2)+(i-j))] = x;
}
 
// Function to store the 
// values in the Matrix 
int Get(struct Matrix m, int i, int j)
{
    if (i >= j)
        return m.A[((m.size)*(j-1)-(((j-2)
                   *(j-1))/2)+(i-j))];
    else
        return 0;
}
 
// Function to display the 
// elements of the matrix 
void Display(struct Matrix m)
{
    // Traverse the matrix
    for (int i = 1; i <= m.size; i++) 
    {
        for (int j = 1; j <= m.size; j++) 
        {
            if (i >= j)
                cout<< m.A[((m.size)*(j-1)-(((j-2)
                       *(j-1))/2)+(i-j))] <<" ";
            else
                cout<<"0 ";
        }
        cout<<endl;
    }
}
 
 
// Function to generate an efficient matrix 
struct Matrix createMat(int Mat[N][N]) 
{ 
    // Declare efficient Matrix 
    struct Matrix mat; 
   
    // Initialize the Matrix 
    mat.size = N; 
    mat.A = (int*)malloc( 
        mat.size * (mat.size + 1) / 2 
        * sizeof(int)); 
   
    // Set the values in matrix 
    for (int i = 1; i <= mat.size; i++) { 
   
        for (int j = 1; j <= mat.size; j++) { 
   
            Set(&mat, i, j, Mat[i - 1][j - 1]); 
        } 
    } 
   
    // Return the matrix 
    return mat; 
} 
 
 
// Driver Code
int main()
{
   
    // Given Input
    int Mat[5][5] = { { 1, 0, 0, 0, 0 },
                      { 1, 2, 0, 0, 0 },
                      { 1, 2, 3, 0, 0 },
                      { 1, 2, 3, 4, 0 },
                      { 1, 2, 3, 4, 5 } };
     
    // Function call to create a memory
    // efficient matrix 
    struct Matrix mat = createMat(Mat); 
   
    // Function call to 
      // print the Matrix 
    Display(mat); 
 
    return 0;
}
 
// This code is contributed by rrrtnx.

C

// C program for the above approach 
#include <stdio.h>
#include <stdlib.h>
 
// Dimensions of the matrix 
const int N = 5;
 
// Structure of a memory 
// efficient matrix
struct Matrix {
    int* A;
    int size;
};
 
// Function to set the 
// values in the Matrix 
void Set(struct Matrix* m, int i, 
         int j, int x)
{
    if (i >= j)
        m->A[((m->size)*(j-1)-(((j-2)
              *(j-1))/2)+(i-j))] = x;
}
 
// Function to store the 
// values in the Matrix 
int Get(struct Matrix m, int i, int j)
{
    if (i >= j)
        return m.A[((m.size)*(j-1)-(((j-2)
                   *(j-1))/2)+(i-j))];
    else
        return 0;
}
 
// Function to display the 
// elements of the matrix 
void Display(struct Matrix m)
{
    // Traverse the matrix
    for (int i = 1; i <= m.size; i++) 
    {
        for (int j = 1; j <= m.size; j++) 
        {
            if (i >= j)
                printf("%d ", 
                       m.A[((m.size)*(j-1)-(((j-2)
                       *(j-1))/2)+(i-j))]);
            else
                printf("0 ");
        }
        printf("\n");
    }
}
 
 
// Function to generate an efficient matrix 
struct Matrix createMat(int Mat[N][N]) 
{ 
    // Declare efficient Matrix 
    struct Matrix mat; 
   
    // Initialize the Matrix 
    mat.size = N; 
    mat.A = (int*)malloc( 
        mat.size * (mat.size + 1) / 2 
        * sizeof(int)); 
   
    // Set the values in matrix 
    for (int i = 1; i <= mat.size; i++) { 
   
        for (int j = 1; j <= mat.size; j++) { 
   
            Set(&mat, i, j, Mat[i - 1][j - 1]); 
        } 
    } 
   
    // Return the matrix 
    return mat; 
} 
 
 
// Driver Code
int main()
{
    // Given Input
    int Mat[5][5] = { { 1, 0, 0, 0, 0 },
                      { 1, 2, 0, 0, 0 },
                      { 1, 2, 3, 0, 0 },
                      { 1, 2, 3, 4, 0 },
                      { 1, 2, 3, 4, 5 } };
     
    // Function call to create a memory
    // efficient matrix 
    struct Matrix mat = createMat(Mat); 
   
    // Function call to 
      // print the Matrix 
    Display(mat); 
 
    return 0;
}

Java

import java.util.Arrays;
 
class Matrix {
    // Structure of a memory
    // efficient matrix
    int size;
    int[][] matrix;
    public Matrix(int size) {
        this.size = size;
        this.matrix = new int[size][size];
    }
 
    // Function to set the
    // values in the Matrix
    public void set(int i, int j, int x) {
        if (i >= j) {
            matrix[i][j] = x;
        }
    }
 
    // Function to store the
    // values in the Matrix
    public int get(int i, int j) {
        if (i >= j) {
            return matrix[i][j];
        } else {
            return 0;
        }
    }
 
    // Function to display the
    // elements of the matrix
    public void display() {
         // Traverse the matrix
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }
}
 
public class Main {
    // Function to generate an efficient matrix
    public static Matrix createMat(int[][] mat) {
        int n = mat.length;
        Matrix matrix = new Matrix(n);
        // Set the values in matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix.set(i, j, mat[i][j]);
            }
        }
        // Return the matrix
        return matrix;
    }
    public static void main(String[] args) {
        // Driver Code
        int[][] mat = {
            {1, 0, 0, 0, 0},
            {1, 2, 0, 0, 0},
            {1, 2, 3, 0, 0},
            {1, 2, 3, 4, 0},
            {1, 2, 3, 4, 5}
        };
        // Function call to create a memory
        // efficient matrix
        Matrix m = createMat(mat);
        // Function call to
        // print the Matrix
        m.display();
    }
}

Python3

class Matrix:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0 for _ in range(size)] for __ in range(size)]
     
    def set(self, i, j, x):
        if i >= j:
            self.matrix[i][j] = x
     
    def get(self, i, j):
        if i >= j:
            return self.matrix[i][j]
        else:
            return 0
     
    def display(self):
        for row in self.matrix:
            print(row)
 
def create_mat(mat):
    n = len(mat)
    matrix = Matrix(n)
    for i in range(n):
        for j in range(n):
            matrix.set(i, j, mat[i][j])
    return matrix
 
if __name__ == '__main__':
    mat = [[1, 0, 0, 0, 0],
           [1, 2, 0, 0, 0],
           [1, 2, 3, 0, 0],
           [1, 2, 3, 4, 0],
           [1, 2, 3, 4, 5]]
 
    m = create_mat(mat)
    m.display()

C#

using System;
 
class Matrix
{
  // Structure of a memory
  // efficient matrix
  private int size;
  private int[,] matrix;
 
  public Matrix(int size)
  {
    this.size = size;
    this.matrix = new int[size, size];
  }
 
  // Function to set the
  // values in the Matrix
  public void Set(int i, int j, int x)
  {
    if (i >= j)
    {
      matrix[i, j] = x;
    }
  }
 
  // Function to store the
  // values in the Matrix
  public int Get(int i, int j)
  {
    if (i >= j)
    {
      return matrix[i, j];
    }
    else
    {
      return 0;
    }
  }
 
  // Function to display the
  // elements of the matrix
  public void Display()
  {
    // Traverse the matrix
    for (int i = 0; i < size; i++)
    {
      for (int j = 0; j < size; j++)
      {
        if (i >= j)
        {
          Console.Write(matrix[i, j] + " ");
        }
        else
        {
          Console.Write("0 ");
        }
      }
      Console.WriteLine();
    }
  }
}
 
class Program
{
  // Function to generate an efficient matrix
  public static Matrix CreateMat(int[,] mat)
  {
    int n = mat.GetLength(0);
    Matrix matrix = new Matrix(n);
    // Set the values in matrix
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
      {
        matrix.Set(i, j, mat[i, j]);
      }
    }
    // Return the matrix
    return matrix;
  }
 
  static void Main(string[] args)
  {
    // Driver Code
    int[,] mat = {
      {1, 0, 0, 0, 0},
      {1, 2, 0, 0, 0},
      {1, 2, 3, 0, 0},
      {1, 2, 3, 4, 0},
      {1, 2, 3, 4, 5}
    };
 
    // Function call to create a memory
    // efficient matrix
    Matrix m = CreateMat(mat);
 
    // Function call to
    // print the Matrix
    m.Display();
  }
}

Javascript

// Dimensions of the matrix
const N = 5;
 
// Structure of a memory
// efficient matrix
class Matrix {
  constructor() {
    this.A = new Array();
    this.size = 0;
  }
}
 
// Function to set the
// values in the Matrix
function Set(m, i, j, x) {
  if (i >= j) {
    m.A[m.size * (j - 1) - ((j - 2) * (j - 1)) / 2 + (i - j)] = x;
  }
}
 
// Function to store the
// values in the Matrix
function Get(m, i, j) {
  if (i >= j) {
    return m.A[m.size * (j - 1) - ((j - 2) * (j - 1)) / 2 + (i - j)];
  } else {
    return 0;
  }
}
 
// Function to display the
// elements of the matrix
function Display(m) {
  // Traverse the matrix
  for (let i = 1; i <= m.size; i++) {
    let row = "";
    for (let j = 1; j <= m.size; j++) {
      if (i >= j) {
        row += m.A[m.size * (j - 1) - ((j - 2) * (j - 1)) / 2 + (i - j)] + " ";
      } else {
        row += "0 ";
      }
    }
    console.log(row);
  }
}
 
// Function to generate an efficient matrix
function createMat(Mat) {
  // Declare efficient Matrix
  let mat = new Matrix();
 
  // Initialize the Matrix
  mat.size = N;
  mat.A = new Array(mat.size * (mat.size + 1) / 2).fill(0);
 
  // Set the values in matrix
  for (let i = 1; i <= mat.size; i++) {
    for (let j = 1; j <= mat.size; j++) {
      Set(mat, i, j, Mat[i - 1][j - 1]);
    }
  }
 
  // Return the matrix
  return mat;
}
 
// Driver Code
let Mat = [
  [1, 0, 0, 0, 0],
  [1, 2, 0, 0, 0],
  [1, 2, 3, 0, 0],
  [1, 2, 3, 4, 0],
  [1, 2, 3, 4, 5],
];
 
// Function call to create a memory
// efficient matrix
let mat = createMat(Mat);
 
// Function call to
// print the Matrix
Display(mat);

Output

Time Complexity: O(N²)
Auxiliary Space: O(N²)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Efficient method to store a Lower Triangular Matrix using Column-major mapping

C++

C

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Google experiments with faster app launch shortcut on Pixel

YouTube gives banned creators a second shot, but with a catch

Pebble sets the stage for its comeback with the revival of its app store

The Pixel Watch 4 shines with its repairability score that’s through the roof

EDITOR PICKS

Google experiments with faster app launch shortcut on Pixel

YouTube gives banned creators a second shot, but with a catch

Pebble sets the stage for its comeback with the revival of its app store

POPULAR POSTS

Google experiments with faster app launch shortcut on Pixel

YouTube gives banned creators a second shot, but with a catch

Pebble sets the stage for its comeback with the revival of its app store

POPULAR CATEGORY

ABOUT US

FOLLOW US