4.1 Linear systems and matrices

A system of \(n\) linear equations in \(n\) unknowns, \begin {align*} a_{11}x_1+a_{12}x_2+\dots +a_{1n}x_n &= b_1,\\ &\ \,\vdots \\ a_{n1}x_1+a_{n2}x_2+\dots +a_{nn}x_n &= b_n, \end {align*}

is written \(A\mathbf x = \mathbf b\), where \(A = (a_{ij})\) is the \(n\times n\) coefficient matrix and \(\mathbf x\), \(\mathbf b\) are column vectors. For hand computation it is convenient to work with the augmented matrix \([A,\mathbf b]\), which carries the right-hand side as an extra column.

Three elementary row operations change a system into an equivalent one, with the same solutions:

(i): multiply equation \(E_i\) by a non-zero constant: \((\lambda E_i)\to (E_i)\);
(ii): add a multiple of equation \(E_j\) to \(E_i\): \((E_i+\lambda E_j)\to (E_i)\);
(iii): interchange two equations: \((E_i)\leftrightarrow (E_j)\).

Each operation can be undone by an operation of the same kind, which is why the solution set does not change.

Theorem 4.1.1. For an \(n\times n\) matrix \(A\) the following are equivalent:

(a): \(A\mathbf x = \mathbf 0\) has only the solution \(\mathbf x = \mathbf 0\);
(b): \(A\mathbf x = \mathbf b\) has a unique solution for every \(\mathbf b\);
(c): \(A\) is nonsingular, that is, \(A^{-1}\) exists;
(d): \(\det A\neq 0\);
(e): Gaussian elimination with row interchanges can be carried out on \(A\mathbf x = \mathbf b\) for every \(\mathbf b\).

This is the basic theorem of linear algebra, and it is proved in linear algebra courses. In this section we take it as known and concentrate on (e): how elimination is carried out, what it costs, and how to keep its errors small.

[next] [front] [up]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.