Sparse Matrix:
A matrix that has minimum number of nonzero elements is called a sparse matrix i.e. very few elements are sparsely distributed in the matrix.
Example: An array of order 3 x 4 containing sparsely located nonzero elements.
0 
1 
2 
3 

0 
0 
25 
0 
7 
1 
0 
0 
2 
8 
2 
0 
0 
1 
0 
(Order 3 x 4)
In the above example, out of 12 elements only 5 elements contain non zero values. Such a matrix is called sparse matrix.
Representation of Sparse Matrix:
 3Tuple Representation
 List Representation
1. 3Tuple Representation: An array of three columns is required. The size of the array is the number of nonzero elements plus one. First row is called the header row that contains total number of rows, total number of columns and nonzero element’s value i.e.
Header Row: Row  Column  Element
rows 
columns 
Elements (non zero) 

0 
3 
4 
5 
1 
0 
1 
25 
2 
0 
3 
7 
3 
1 
2 
2 
4 
1 
3 
8 
5 
2 
2 
1 
Sparse Matrix representation for the array given above
Number of rows: 3
Number of columns: 4
Number of elements: 5
Order of Sparse Matrix = (5+1) x 3 = 6 x 3.
2. List Representation: Each row is converted to a node in linked representation where each node contains, row subscripts, column subscript and nonzero element. The first node returns the total number of rows, columns and elements.
Example:
345 > 0125 > 037 > 122 > 138 > 221 > NULL
Array representation of Sparse Matrix
Linked representation of Sparse Matrix