Trong phần này, chúng ta sẽ xem ma trận thưa là gì và cách biểu diễn chúng trong bộ nhớ. Một ma trận được gọi là ma trận thưa nếu hầu hết các phần tử của nó bằng 0. Định nghĩa khác: ma trận có tối đa 1/3 phần tử khác 0 (khoảng 30% của m x n) được gọi là ma trận thưa.
Chúng ta sử dụng ma trận trong bộ nhớ máy tính để thực hiện các phép toán hiệu quả. Nhưng nếu ma trận có tính chất thưa, dù có giúp thực hiện phép toán hiệu quả, nó sẽ chiếm dụng không gian bộ nhớ lớn mà không có mục đích. Do đó, ta sẽ sử dụng các cấu trúc khác để lưu trữ ma trận thưa.
Giả sử ta có ma trận thưa như sau:

Như ta thấy, có 8 phần tử khác 0 và 28 giá trị 0. Ma trận này chiếm 6*6 = 36 ô nhớ. Nếu kích thước ma trận lớn hơn, lãng phí không gian sẽ tăng lên.
Ta có thể lưu thông tin về ma trận thưa bằng cấu trúc bảng. Giả sử ta tạo bảng X như sau:

Cột đầu tiên chứa số hàng, cột thứ hai chứa số cột. Cột thứ ba chứa dữ liệu tại M[hàng, cột]. Mỗi hàng của bảng này gọi là bộ ba (triplet), vì có ba tham số. Bộ ba đầu tiên chứa thông tin kích thước ma trận. Hàng = 6 và Cột = 6 cho biết ma trận M là ma trận 6x6. Trường giá trị biểu thị số phần tử khác 0 có trong mảng.
Bảng này cũng chiếm 9 * 3 = 36 đơn vị không gian, vậy đâu là phần thắng? Nếu kích thước ma trận là 8*8 = 64, nhưng chỉ có 8 phần tử, thì bảng X vẫn chỉ chiếm 36 đơn vị. Ta thấy có 3 cột cố định, số hàng thay đổi theo số phần tử khác 0. Nếu có T phần tử khác 0, độ phức tạp không gian là O(3*T) = O(T). Còn ma trận thông thường là O(m x n).