Sparse Matrix - Transpose and Addition

 A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial. As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix. Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly.

In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero.

Such a matrix is called a Sparse Matrix.
Formally:

A matrix in which the number of zero elements is significantly greater than the number of non-zero elements.

The opposite of a sparse matrix is a Dense Matrix, where most of the elements are non-zero.

Here's a detailed description of sparse matrices, including their representation and common operations:

Example 

Let's take the example of a movie recommendation system. There are millions of users and thousands of movies, so it's not possible for users to watch and rate all movies. This data can be represented as a matrix where the rows are the users, and the columns are the movies.

Most of the matrix elements will be empty, where the missing values will be replaced with zeros. Since a small percentage of the matrix has non-zero values, this matrix can be considered a sparse matrix. A small portion of the data is given below:

Sparsity

Sparsity is simply a way of describing how many zero elements a matrix has compared to its total size.

In other words:

Sparsity = the proportion of zero elements in the matrix.

It’s a measure of “how sparse” the matrix is.
A matrix with high sparsity has mostly zero entries.

---

Formula

If:

• $m$ = number of rows

• $n$ = number of columns

• $NZ$ = number of non-zero elements

Then:

$$\text{Sparsity} = \frac{\text{Number of zero elements}}{\text{Total number of elements}}$$

Since total elements = $m \times n$ and zero elements = $m \times n - NZ$

$$\text{Sparsity} = \frac{m \times n - NZ}{m \times n}$$

---

Example

Matrix:

$$\begin{bmatrix} 0 & 0 & 0 & 5 \\ 0 & 8 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

• Dimensions: $3 \times 4 = 12$ total elements

• Non-zero elements: 2 (5 and 8)

• Zero elements: $12 - 2 = 10$
  

$$\text{Sparsity} = \frac{10}{12} \approx 0.833 \; \text{or} \; 83.3\%$$

This means 83% of the matrix is zeros — a highly sparse matrix.

---

Interpretation

• High sparsity (close to 1 or 100%) → very few non-zero elements → a sparse matrix.

• Low sparsity (close to 0) → many non-zero elements → a dense matrix.

In a sparse matrix, the majority of elements are zero, and only the non-zero elements carry meaningful information for data analysis. Representing such a matrix in conventional two-dimensional array form results in significant memory wastage. Moreover, operations that require accessing non-zero elements must still scan the entire matrix, thereby incurring unnecessary computational overhead and increasing the time complexity of the process.

To overcome the inefficiencies of conventional storage, sparse matrices are represented using specialized data structures that store only the non-zero elements along with their positions. Such representations significantly reduce memory requirements and improve processing efficiency by eliminating unnecessary scans of zero elements. Common techniques include the triplet form (row, column, value), compressed row and column storage, and linked representations. These methods enable faster traversal, addition, and multiplication of sparse matrices while maintaining compact storage.

If we store a large sparse matrix in a standard 2D array:

• We waste memory storing zeros.

• We waste computation time when processing useless zero elements.

Instead, we can store only the non-zero elements and their positions — saving memory and making computations faster.

The following is a 3 tuple(triplet)  representation.The first row of sparse matrix always specifies the number of rows, number of columns and number of non zero elements in the sparse matrix.The second row onwards , non zero elements are represented with corresponding row and column.

Advantages:

• Memory Efficiency: Store only non-zero values.
• Speed: Skip useless zero-element computations.
• Scalability: Handle large problems (e.g., adjacency matrices in graphs).

Disadvantages:

• Random access to elements is slower.
• Still requires space for three integers per non-zero value.
• Some algorithms need to be redesigned to work efficiently.

 Applications

• Graph Representations: Adjacency matrices for large sparse graphs.
• Finite Element Analysis: Physics and engineering simulations.
• Image Processing: Large images with mostly blank pixels.
• Search Engines: Term-document matrices in NLP.

Triplet Representation 

Algorithm idea:

1. Scan the entire $m \times n$ matrix element by element.

2. For each non-zero element, store its (row, column, value) in the sparse list.

Steps:

• Total elements to check = $m \times n$
  

• Checking each element takes $O(1)$.

• Therefore, the scanning step = $O(m \times n)$
  

• Storing the non-zero elements also takes $O(NZ)$, where $NZ$ is the number of non-zero elements, but since $NZ \le m \times n$, the total complexity is still $O(m \times n)$
  

---

Conclusion

• Time Complexity: $O(m \times n)$
  

• Space Complexity: $O(NZ)$

   (plus a small overhead for metadata like rows, columns, and count).

C program - 3-Tuple(Triplet)  Representation

#include <stdio.h>
struct Sparse {
int row;
int col;
int value;
};

int main() {
// Original 4x5 matrix
int matrix[4][5] = {
{0, 0, 0, 5, 0},
{0, 8, 0, 0, 0},
{0, 0, 0, 0, 0},
{1, 0, 0, 0, 4}
};

struct Sparse sparse[20]; // Enough space
int rows = 4, cols = 5, k = 1; // k starts from 1 (0 for metadata)

// Metadata: dimensions and number of non-zero elements
sparse[0].row = rows;
sparse[0].col = cols;
sparse[0].value = 0; // Will be updated later

// Store non-zero elements
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] != 0) {
sparse[k].row = i;
sparse[k].col = j;
sparse[k].value = matrix[i][j];
k++;
}
}
}

sparse[0].value = k - 1; // Total non-zero count

// Print sparse representation
printf("Row Col Value\n");
for (int i = 0; i < k; i++) {
printf("%d %d %d\n", sparse[i].row, sparse[i].col, sparse[i].value);
}
return 0;
}

Row    Col     Value

4           5           4

0           3           5

1           1           8

3           0           1

3           4           4

Operations on Sparse Matrices

When stored efficiently, we can still perform:

• Transpose: Swap row and column indices in each triplet.

• Addition: Merge two triplet lists, adding matching positions.

---

Transpose of a Sparse Matrix

Transpose of a matrix means rows become columns and columns become rows.
In sparse matrix representation, for each term, swap row and column.

Example:

Consider a 3x3 matrix

0     5     0

3     0     0

0     0     6

Sparse Representation (with Metadata):

(First row is metadata: rows, columns, total non-zero elements.)

Index	Row	Column	Value
0	3	3	3
1	0	1	5
2	1	0	3
3	2	2	6

Now let's find Transpose

Transpose means swapping the row and column for each element.

Metadata for transpose:

• Rows become Columns

• Columns become Rows

So metadata: (3, 3, 3)

So the transposed sparse matrix (with metadata):

Index	Row	Column	Value
0	3	3	3
1	0	1	3
2	1	0	5
3	2	2	6

And if you reconstruct the full matrix from this sparse data, it will look like:

0     3     0

5     0     0

0     0     6

Algorithm: Transpose of Sparse Matrix

Input:

• A sparse matrix sparse[] in 3-tuple form where:

  • sparse[0] stores (number of rows, number of columns, number of non-zero elements).

  • sparse[1..n] store (row, column, value) of non-zero elements.

Output:

• transpose[] array representing the transposed matrix.

---

Steps:

1. Read the sparse[] array, including metadata and non-zero elements.

2. Initialize the first element (transpose[0]) of transposed matrix:

   • transpose[0].row = sparse[0].col

   • transpose[0].col = sparse[0].row

   • transpose[0].value = sparse[0].value

3. For each column i (0 to number of columns - 1) of the original matrix:

   • For each non-zero element (from index 1 to n):

     • If the column index j of the element is i:

       • Create a new entry in transpose[]:

         • transpose[k].row = sparse[j].col

         • transpose[k].col = sparse[j].row

         • transpose[k].value = sparse[j].value

       • Increment k.

4. End

---

🔔 Key Notes:

• We scan column-wise to maintain the order of the transposed sparse matrix.

• The metadata must be swapped (rows ↔ columns) at the start.

• The number of non-zero elements remains the same after transpose.

Time Complexity:

• For each of the $n$ columns, we scan all $NZ$ triplets.

• Complexity: $O(n \times NZ)$— which can be quite large if $n$ is big.

Implementation of Transpose in C 

#include <stdio.h>

struct Term {

    int row;

    int col;

    int value;

};

void transpose(struct Term sparse[], struct Term transpose[]) {

    int i, j, n;

    n = sparse[0].value; // number of non-zero elements

    // Step 1: Metadata for transpose

    transpose[0].row = sparse[0].col;

    transpose[0].col = sparse[0].row;

    transpose[0].value = sparse[0].value;

    // Step 2: Swap row and col for each non-zero element

    int k = 1; // index for transpose array

    for (i = 0; i < sparse[0].col; i++) { // for each column of original

        for (j = 1; j <= n; j++) {         // check all elements

            if (sparse[j].col == i) {

                transpose[k].row = sparse[j].col;

                transpose[k].col = sparse[j].row;

                transpose[k].value = sparse[j].value;

                k++;

            }

        }

    }

}

void display(struct Term sparse[]) {

    int n = sparse[0].value; // number of non-zero elements

    printf("Row  Col  Value\n");

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

        printf("%3d %4d %5d\n", sparse[i].row, sparse[i].col, sparse[i].value);

    }

}

int main() {

    int rows, cols, n;

    printf("Enter number of rows, columns, and non-zero elements: ");

    scanf("%d %d %d", &rows, &cols, &n);

    struct Term sparse[50], transposed[50];

    sparse[0].row = rows;

    sparse[0].col = cols;

    sparse[0].value = n;

    printf("Enter the non-zero elements (row column value):\n");

    for (int i = 1; i <= n; i++) {

        scanf("%d %d %d", &sparse[i].row, &sparse[i].col, &sparse[i].value);

    }

    printf("\nOriginal Sparse Matrix Representation:\n");

    display(sparse);

    transpose(sparse, transposed);

    printf("\nTransposed Sparse Matrix Representation:\n");

    display(transposed);

    return 0;

}

Output

Enter number of rows, columns, and non-zero elements: 3 3 3

Enter the non-zero elements (row column value):

0 1 5

1 0 3

2 2 6

Original Sparse Matrix Representation:

Row  Col  Value

  3    3     3

  0    1     5

  1    0     3

  2    2     6

Transposed Sparse Matrix Representation:

Row  Col  Value

  3    3     3

  0    1     3

  1    0     5

  2    2     6

*************************************

Addition of Sparse Matrix

Lets consider two sparse matrix representation A and B

A:

Index	Row	Column	Value
0	3	3	3
1	0	0	5
2	0	2	7
3	2	1	6

B:

Index	Row	Column	Value
0	3	3	2
1	0	0	3
2	2	2	8

Perform Addition

• Compare A[1] and B[1]:

  • Same position (0,0). Add values: 5 + 3 = 8 → (0,0,8) copy the result

  • Note if the sum is zero, do not copy

• Compare A[2] and B[2]:

  • A[2] (0,2) comes before B[2] (2,2). Copy A[2] → (0,2,7)

• Now A[3] and B[2]:

  • A[3] (2,1) comes before B[2] (2,2). Copy A[3] → (2,1,6)

• No more A. Now copy remaining B[2] → (2,2,8)

Resultant Sparse Matrix C

Index	Row	Column	Value
0	3	3	4
1	0	0	8
2	0	2	7
3	2	1	6
4	2	2	8

Algorithm: Addition of Two Sparse Matrices

---

Input:

• Two sparse matrices A[] and B[] (both in 3-tuple form with metadata in the first row).

• Each row of A[] and B[] has (row, column, value).

Output:

• A sparse matrix C[] representing A + B.

---

Steps

1. Initialize pointers i = 1 for A and j = 1 for B (metadata is in index 0).

2. Compare (row, col) of A[i] and B[j].

3. If positions are equal → sum values and store if non-zero, increment both i and j.

4. If A[i] comes before B[j] → copy A[i] to result, increment i.

5. If B[j] comes before A[i] → copy B[j] to result, increment j.

6. Append any remaining terms from A or B.

Steps in detail :

1. Check if the matrices have the same dimensions:

   • If A[0].row != B[0].row or A[0].col != B[0].col,
     then Addition is not possible. Stop.

2. Initialize pointers:

   • i = 1 (for A[])

   • j = 1 (for B[])

   • k = 1 (for C[])

3. Set C[0] metadata:

   • C[0].row = A[0].row

   • C[0].col = A[0].col

   • C[0].value = 0 (for now; update later)

4. Compare and Merge:

   • While i <= A[0].value and j <= B[0].value, do:

     • If (A[i].row < B[j].row) or
       (A[i].row == B[j].row and A[i].col < B[j].col):

       • Copy A[i] to C[k]

       • Increment i and k

     • Else if (B[j].row < A[i].row) or
       (B[j].row == A[i].row and B[j].col < A[i].col):

       • Copy B[j] to C[k]

       • Increment j and k

     • Else (Same position):

       • Add the values: sum = A[i].value + B[j].value

       • If sum != 0:

         • C[k].row = A[i].row

         • C[k].col = A[i].col

         • C[k].value = sum

         • Increment k

       • Increment both i and j

5. Copy Remaining Elements:

   • While i <= A[0].value:

     • Copy A[i] to C[k]

     • Increment i and k

   • While j <= B[0].value:

     • Copy B[j] to C[k]

     • Increment j and k

6. Update Metadata:

   • Set C[0].value = k - 1

7. End

---

🧠 Key Points:

• Matrices must be sorted by (row, column).

• If two elements overlap (same row and column), add their values.

• If the result of addition is zero, do not insert it into the result sparse matrix.

Time Complexity

Let:

• $NZ_A$ = number of non-zero elements in matrix A

• $NZ_B$ = number of non-zero elements in matrix B

When both triplet lists are sorted by row, then column, addition is done by merging them — similar to merging two sorted arrays.

Time Complexity:

$$T(N) = O(NZ_A + NZ_B)$$

• Each non-zero element is compared at most once.

• Comparisons and insertions are $O(1)$.

C Program for Sparse Matrix Addition

#include <stdio.h>

#define MAX 100

// Define structure for Sparse Matrix elements

typedef struct {

    int row;

    int col;

    int value;

} Element;

int main() {

    Element A[MAX], B[MAX], C[MAX];

    int i, j, k;

    

    int m, n, tA, tB; // rows, columns, non-zero elements in A and B

    // Input Sparse Matrix A

    printf("Enter rows, columns and number of non-zero elements of Matrix A: ");

    scanf("%d %d %d", &A[0].row, &A[0].col, &A[0].value);

    tA = A[0].value;

    printf("Enter elements (row column value) for Matrix A:\n");

    for(i = 1; i <= tA; i++) {

        scanf("%d %d %d", &A[i].row, &A[i].col, &A[i].value);

    }

    // Input Sparse Matrix B

    printf("Enter rows, columns and number of non-zero elements of Matrix B: ");

    scanf("%d %d %d", &B[0].row, &B[0].col, &B[0].value);

    tB = B[0].value;

    printf("Enter elements (row column value) for Matrix B:\n");

    for(i = 1; i <= tB; i++) {

        scanf("%d %d %d", &B[i].row, &B[i].col, &B[i].value);

    }

    // Check if addition possible

    if(A[0].row != B[0].row || A[0].col != B[0].col) {

        printf("Addition not possible. Matrix dimensions do not match.\n");

        return 0;

    }

    i = j = k = 1; // Initialize pointers

    C[0].row = A[0].row;

    C[0].col = A[0].col;

    // Merge and Add

    while(i <= tA && j <= tB) {

        if(A[i].row < B[j].row || (A[i].row == B[j].row && A[i].col < B[j].col)) {

            C[k++] = A[i++];

        }

        else if(B[j].row < A[i].row || (B[j].row == A[i].row && B[j].col < A[i].col)) {

            C[k++] = B[j++];

        }

        else { // Same position

            int sum = A[i].value + B[j].value;

            if(sum != 0) {

                C[k].row = A[i].row;

                C[k].col = A[i].col;

                C[k].value = sum;

                k++;

            }

            i++;

            j++;

        }

    }

    // Copy remaining elements of A

    while(i <= tA) {

        C[k++] = A[i++];

    }

    // Copy remaining elements of B

    while(j <= tB) {

        C[k++] = B[j++];

    }

    C[0].value = k - 1; // Update number of non-zero elements

    // Display Result

    printf("\nResultant Sparse Matrix (row column value):\n");

    for(i = 0; i < k; i++) {

        printf("%d %d %d\n", C[i].row, C[i].col, C[i].value);

    }

    return 0;

}

Output

Enter rows, columns and number of non-zero elements of Matrix A: 3 3 3

Enter elements (row column value) for Matrix A:

0 0 5

0 2 7

2 1 6

Enter rows, columns and number of non-zero elements of Matrix B: 3 3 2

Enter elements (row column value) for Matrix B:

0 0 3

2 2 8

Resultant Sparse Matrix (row column value):

3 3 4

0 0 8

0 2 7

2 1 6

2 2 8