Sparse Matrix

A sparse matrix is a matrix where most of the entries are zero, and storing every one of those zeros is wasted effort, so here's a compact way to represent one and how to transpose it correctly.

What makes a matrix sparse?

Consider this matrix:

Out of 20 entries, only 3 are non-zero (highlighted). Storing all 20, most of them zero, wastes space for no benefit: a zero entry carries no information the reader couldn't already assume by default.

This is the same motivation behind the sparse polynomial representation covered just before this: skip storing what is overwhelmingly absent, and only record what's actually there.

Tuple representation

Instead of storing every cell, a sparse matrix stores only its non-zero entries, each as a triple:

(row, column, value)

The very first tuple is reserved for metadata, holding the matrix's dimensions and how many non-zero entries follow:

(number of rows, number of columns, number of non-zero elements)

Example

For the matrix above, the non-zero entries are:

Matching each highlighted cell above to its tuple: row 0, col 4 holds 7; row 2, col 1 holds 5; row 3, col 4 holds 2. The table on the right is the same 3 tuples, with a shaded metadata row on top holding the matrix's dimensions and non-zero count: 4 rows, 5 columns, 3 non-zero elements. Only 4 rows of table describe a matrix that would otherwise need 20 stored values, and the saving gets larger the sparser (and bigger) the matrix is.

Transpose of a sparse matrix

Transposing a matrix is a common step before other operations, matrix multiplication, solving systems of equations, and several graph algorithms all rely on it, so it's worth knowing how to do it efficiently on a sparse matrix rather than falling back to the full, mostly-zero form.

The transpose of a matrix swaps rows and columns: entry (i, j) becomes (j, i). For a sparse matrix in tuple form, that sounds like it should just mean swapping the row and column fields of every tuple. It's not quite that simple.

Every row of A becomes a column of T, and vice versa: row 0 of A (which had the 7 at column 4) becomes column 0 of T, so that 7 now sits at row 4, column 0. The algorithm below produces exactly this T, correctly stored in row-major tuple form. Getting there needs more care than it first appears.

Why a simple swap fails

Tuples are stored in row-major order: sorted by row first, then by column within each row. If you swap row and column in each tuple while keeping the original order, the result is no longer sorted correctly:

Original A (row-major):
(0, 4, 7)
(2, 1, 5)
(3, 4, 2)
 
Simple swap (row, col exchanged, order unchanged):
(4, 0, 7)   <- row 4
(1, 2, 5)   <- row 1
(4, 3, 2)   <- row 4
 
NOT sorted by row! Row 1 appears after row 4.

Since the transpose must also be valid row-major tuple form, this broken ordering isn't just untidy, it defeats the format's own assumptions and would misread as a different matrix.

The correct approach

To keep the result in row-major order, don't just swap and reorder afterward. Instead, build the transpose by scanning column by column: for each column of the original matrix, in order, find every non-zero entry that belongs to it and place it next. Since a column of A becomes a row of the transpose, walking A's columns in order naturally produces T's rows in order.

SparseTranspose(A, T)
 
Input:  A - sparse matrix in tuple form (row-major)
Output: T - transpose of A (row-major)
 
1. T.rows = A.columns
2. T.columns = A.rows
3. T.nonZero = A.nonZero
4. next = 0
 
5. For col = 0 to A.columns - 1:
       For each non-zero element A[k]:
           If A[k].column == col:
               T[next].row = A[k].column
               T[next].column = A[k].row
               T[next].value = A[k].value
               next = next + 1

The inner loop scans all of A's tuples once for every column of A, so this takes O(columns x non-zero terms) time, more than a single pass, but it's the price of producing correctly-ordered output directly instead of sorting afterward.

Worked example

Original matrix A (4 x 5):

Tuple form of A, row-major:

Scanning column by column:

col = 0: no non-zero elements
col = 1: (2, 1, 5) -> swap -> (1, 2, 5) -> append to T
col = 2: no non-zero elements
col = 3: no non-zero elements
col = 4: (0, 4, 7) -> swap -> (4, 0, 7) -> append to T
         (3, 4, 2) -> swap -> (4, 3, 2) -> append to T

Result T (5 x 4, row-major):

Which corresponds to the matrix:

Notice the rows of T are already in order, 1 before 4, exactly because the algorithm visited A's columns in order.

Quick recall

• A sparse matrix stores far more zeros than non-zero values, so storing every cell wastes space.
• Tuple representation stores only (row, column, value) triples, with a metadata tuple giving the dimensions and non-zero count.
• Swapping row and column per tuple is not enough to transpose correctly, the result can end up out of row-major order.
• The correct transpose scans the original matrix column by column, so entries land in the transpose already sorted by row.