# Sparsity

The fraction of zeroes in a matrix. If $LaTeX: \textstyle A$ is $LaTeX: \textstyle m \times n,$ and $LaTeX: \textstyle A_{(i, j)} \ne 0$ for $LaTeX: k$ of its elements, its sparsity is $LaTeX: \textstyle \frac{k}{mn}.$ Large linear programs tend to be very sparse, increasingly so as the dimensions grow. For example, consider the standard transportation problem with s sources and d destinations. This has $LaTeX: \textstyle m = (s+d)$ constraints and $LaTeX: \textstyle n = sd$ variables. Each column, however, has exactly 2 nonzeroes since A is the incidence matrix of the network, so its sparsity is $LaTeX: \textstyle \frac{2n}{mn} = \frac{2}{m},$ which decreases as the number of sources and/or destinations grows large.