Linear Equations

alt text 

Linear equations have been around for thousands of years. The picture on the left shows a 17th century Chinese text that explains the ancient art of fangcheng (‘‘rectangular arrays’’, for more details see here). Linear equations arise naturally in many areas of engineering, often as simple models of more complicated, non-linear equations. They form the core of linear algebra, and often arise as constraints in optimization problems. They are also an important building block of optimization methods, as many optimization algorithms rely on linear equations.

Linear equations can be expressed as Ax=y, where x in mathbf{R}^n is the unknown, y in mathbf{R}^m is a given vector, and A in mathbf{R}^{m times n} is a matrix. The set of solutions is an affine set. In turn, any affine set can be described as the set of solutions to an affine equation.

The issue of existence and unicity of solutions lead to important notions attached to the associated matrix A. The nullspace, which contains the input vectors that are crushed to zero by the associated linear map x rightarrow Ax; the range, which contains the set of output vectors that is attainable by the linear map; and its dimension, the rank. There is a variety of solution methods for linear equations; we describe how the QR decomposition of a matrix can be used in this context.