Sparse Matrices and Special Arrays

A sparse matrix has most entries zero. Storing it fully wastes space, so we use a triplet (3-tuple) representation: each non-zero element is stored as (row, column, value). The table typically has a header row recording (total rows, total columns, number of non-zeros). For a matrix with t non-zero elements, storage is (t+1) rows x 3 columns. Memory aid: 'one row per non-zero, plus one header.' This saves space only when t is small relative to mn; the break-even point is roughly when 3(t+1) < m*n. Other formats include CSR (Compressed Sparse Row) and CSC, which compress further by storing row pointers.

A lower-triangular n x n matrix has only i >= j entries non-zero, totaling n(n+1)/2 elements; storing these in a 1-D array saves ~half the space. Row-major index of A[i][j] (1-based, i>=j) in the packed array = i(i-1)/2 + (j-1). Memory aid: 'rows above contribute 1+2+...+(i-1) = i(i-1)/2 elements.' An upper-triangular matrix is symmetric to this. A symmetric matrix also needs only n(n+1)/2 stored values since A[i][j]=A[j][i]. A tridiagonal (banded) matrix has at most 3n-2 non-zero elements (main diagonal n, plus two adjacent diagonals of n-1 each).

Store a 1-based lower-triangular matrix row by row in a 1-D array. Find the array index (0-based) of A[4][2].

Elements before row 4 = rows 1,2,3 have 1+2+3 = 6 elements = 34/2 using i(i-1)/2 with i=4 -> 43/2 = 6.
Within row 4, A[4][2] is the 2nd element, offset (j-1) = 1.
Index = 6 + 1 = 7 (0-based), i.e., the 8th stored element.

Formula check: i(i-1)/2 + (j-1) = 4*3/2 + (2-1) = 6 + 1 = 7. Memory aid: 'triangular numbers count the rows above, then add the column offset within the current row.'

Cover the answer, recall, then check. 12 cards on sparse and special-matrix storage.

Q1. What is a sparse matrix?
A1. A matrix in which most elements are zero, so only the non-zero entries are worth storing.

Q2. Triplet (COO) representation stores what per non-zero element?
A2. Row index, column index, and value.

Q3. A header row is often added to the triplet list — what does it hold?
A3. Number of rows, number of columns, and count of non-zero elements.

Q4. Number of (potentially non-zero) elements in an n×n lower-triangular matrix?
A4. n(n+1)/2.

Q5. Elements stored for an n×n diagonal matrix?
A5. n (only the main diagonal).

Q6. Number of non-zero elements in an n×n tridiagonal matrix?
A6. 3n − 2 (n main + (n−1) upper + (n−1) lower diagonal).

Q7. Storage for a symmetric n×n matrix?
A7. n(n+1)/2 — store one triangle (incl. diagonal); A[i][j] = A[j][i].

Q8. Lower-triangular, row-major, 1-indexed: linear offset (0-based) of A[i][j], i ≥ j?
A8. i(i−1)/2 + (j − 1). Elements before row i = 1+2+…+(i−1) = i(i−1)/2.

Q9. Elements stored for an n×n upper-triangular matrix?
A9. n(n+1)/2.

Q10. CSR (Compressed Sparse Row) uses which three arrays?
A10. values, column-indices, and row-pointers (offsets where each row starts).

Q11. When is a sparse representation worthwhile?
A11. When the number of non-zeros ≪ n², so space and per-operation cost drop below the dense O(n²).

Q12. Trade-off of switching to a sparse representation?
A12. Saves space but loses O(1) random access — locating A[i][j] needs a search/scan.

When a matrix is mostly zeros, storing all n² cells wastes space and time. Sparse and "special" matrices exploit structure to store only what matters — a favourite GATE spot for storage-count and address-arithmetic numericals.

Sparse matrix representations

• Triplet / COO (coordinate): a list of (row, col, value) for each non-zero, usually with a header row (#rows, #cols, #non-zeros). Storage ≈ 3k values for k non-zeros (+ header).
• Linked-list representation: node per non-zero, linked row-wise or column-wise — easier insert/delete than triplets.
• CSR (Compressed Sparse Row): three arrays — values, column-indices, and row-pointers. Compact and fast for row traversal / matrix–vector multiply. CSC is the column analogue.

Special (structured) matrices — storage

Matrix type (n×n)	Elements stored	Note
Diagonal	n	only main diagonal
Tridiagonal	3n − 2	main + 2 adjacent diagonals
Lower/Upper triangular	n(n+1)/2	one triangle incl. diagonal
Symmetric	n(n+1)/2	A[i][j] = A[j][i]
Dense (no structure)	n²	baseline

Address arithmetic (lower-triangular, row-major, 1-indexed)

Number of elements before row i = 1 + 2 + … + (i−1) = i(i−1)/2. So the 0-based linear offset of A[i][j] (with i ≥ j) is:
offset = i(i−1)/2 + (j − 1), and byte address = Base + offset·w.

Exam Tricks & Tips

• 🎯 Memorise the four counts: diagonal n, tridiagonal 3n−2, triangular/symmetric n(n+1)/2. These are asked directly.
• 🎯 Triangular offset trick: the "triangular number" i(i−1)/2 counts all cells above row i — the whole address formula falls out of it.
• 🎯 Tridiagonal is 3n−2, not 3n: the two off-diagonals each have only n−1 entries (corners missing).
• 🎯 Symmetric = same storage as triangular (n(n+1)/2), because half the matrix is redundant.
• 🎯 Sparse pays off only when non-zeros ≪ n²; for a nearly full matrix, triplets can cost more than dense storage (3 numbers per entry).
• ❌ Common mistake: forgetting the diagonal — a strict lower triangle (i > j) has n(n−1)/2 cells; including the diagonal (i ≥ j) gives n(n+1)/2.

Expected exam pattern

1–2 mark numericals: "How many elements must be stored for an n×n tridiagonal / triangular matrix?", or "Find the address of A[i][j] in a lower-triangular matrix stored row-wise." Occasionally a triplet-count or CSR-array-size question.

Quick recap

Store only non-zeros: triplets (row, col, value), linked lists, or CSR. Special matrices have fixed counts — diagonal n, tridiagonal 3n−2, triangular/symmetric n(n+1)/2. Triangular address offset = i(i−1)/2 + (j−1). Sparse saves space but trades away O(1) random access.