Consider an m by n matrix of real numbers. Such a matrix is called sparse if most of the entries in the matrix are zeroes. Sparse matrices are quite common in many engineering applications (especially those that involve solving partial differential equations) and many numerical software packages try to take advantage of the sparsity of a matrix to reduce the memory used to store the matrix. Reducing memory usage can sometimes speed up associated algorithms as well.
One can reduce the amount of memory it takes to store a sparse matrix by just keeping track of the nonzero entries. For example, suppose we have a 100 by 500 matrix of reals with the rows labeled 0, 1,...,99 and the columns labeled 0, 1,...,499. Now suppose that the only nonzeroes in the matrix are in positions (0, 5), (1, 10), and (25, 50). Then, rather than store the entire 100 by 500 matrix, it makes sense to just store the three positions and the corresponding nonzero reals. Compressing sparse matrices is a well-researched area and there are many well-known formats for compressed sparse matrices such as the Harwell-Boeing format, Compressed Row Storage, Compressed Column Storage, Block Compressed Row Storage, Compressed Diagonal Storage, Jagged Diagonal Storage, Skyline Storage, etc. Feel free to follow these links if you want to read more.
Problem: Let us suppose that we want to store a square sparse matrix in the Compressed Row Storage format. Recall that for a square matrix the number of rows and columns are identical.