Linear equations

A system of m equations in n unknowns

can be written in matrix notation as

with the coefficient matrix:

We have to distinguish the following three cases:

overdetermined	exactly determined	underdetermined
m>n	m = n	m < n

Such systems can be consistent and have solutions, or inconsistent and then have no solution, as shown in the following figure representing three equations with three unknowns (three planes). The two systems in the top row are consistent: system a has one point as the unique solution and system b has all points of a straight line as solutions. The three systems in the bottom line (c, d, e) are inconsistent and have no solution.

An underdetermined system (m < n) does not have a unique solution; it can be consistent with infinitely many solutions or inconsistent, with no solution, as can be seen in the above picture. If one removes in the above picture one plane, then all systems will have infinitely many solutions except for system c, which has no solution.

In the case of more equations than unknowns (m > n) the system is usually inconsistent and does not have any solution. Adding more planes to the plots in the above picture could leave the systems a and b consistent only if they pass exactly through the intersecting point or line. In some inconsistent (overdetermined) cases, approximate solutions can be found, if additional criteria are introduced ( Fitting).

To solve Ax = b, one can choose between many different methods depending on A. If A

is

	upper (lower) triangular	:	backward (forward) substitution
	symmetric and positive definite	:	Cholesky Decomposition
	not triangular	:	Gaussian Elimination
	square and many right sides	:	LU Decomposition
	non square	:	QR Decomposition
	any matrix (e.g. ill-conditioned)	:	Singular Value Decomposition.

The computing time increases in the above order. The advantage of orthogonalization methods (QR and SVD) is that they can be applied to all systems, producing stable solutions without accumulation of rounding errors (see Golub89).