information:classification
Underdetermined linear systems

A system of m linear equations in n unknowns is underdetermined if it has more than one solution. This occurs when the matrix of the system and its augmented matrix have the same rank r and r < n. In this case, one can select n − r unknowns as parameters and represent all solutions as a parametric equation where all unknowns are expressed as linear combinations of the selected ones. That is, if the unknowns are x 1, …, x n, {\displaystyle x_{1},\ldots,x_{n},} one can reorder them for expressing the solutions as

x 1 = β 1 + ∑ j = r + 1 n α 1, j x j ⋮ x r = β r + ∑ j = r + 1 n α r, j x j x r + 1 = x r + 1 ⋮ x n = x n. {\displaystyle {\begin{aligned}x_{1}&=\beta _{1}+\sum _{j=r+1}^{n}\alpha _{1,j}x_{j}\\\vdots \\x_{r}&=\beta _{r}+\sum _{j=r+1}^{n}\alpha _{r,j}x_{j}\\x_{r+1}&=x_{r+1}\\\vdots \\x_{n}&=x_{n}.\end{aligned}}}

Such a parametric equation is called a parametric form of the solution of the system.

The standard method for computing a parametric form of the solution is to use Gaussian elimination for computing a reduced row echelon form of the augmented matrix. Then the unknowns that can be used as parameters are the ones that correspond to columns not containing any leading entry (that is the left most non zero entry in a row or the matrix), and the parametric form can be straightforwardly deduced.