Matrices and systems of linear equations
A matrix is in rowechelon form if:

all zero rows (if any) are at the bottom of the matrix

if two successive rows are nonzero, the second starts with
more zeros than the first (moving from left to right).
The leading (leftmost nonzero) entry of a row (if any) is
called a pivot.
A matrix is in reduced rowechelon form if it is in
rowechelon form and

the pivot entry in each nonzero row is 1

all other elements of the column in which the leading entry 1
occurs are zeros.
Examples

The matrix is in rowechelon form.

The matrix is not in rowechelon
form.

The matrix is in reduced
rowechelon form.

The matrix and the matrix are not in reduced rowechelon form.
The following three operations are called elementary row
operations:

Interchanging two rows:
R_{i}↔R_{j}
interchanges rows i and j.

Multiplying a row by a nonzero scalar:
R_{i}→cR_{i}
multiplies row i by the real number c.

Adding a multiple of one row to another row:
R_{i}→R_{i}+
cR_{j} adds c times row j to
row i.
Matrix A is rowequivalent to matrix
B if B is obtained from A by a
sequence of elementary row operations.
Example
Given the matrix ; R_{2}
→ R_{2} + 2R_{3} ; R_{2} → R_{3}
; R_{1} →
2R_{1} . A
and B are rowequivalent.
It's not difficult to prove that if A and
B are rowequivalent augmented matrices of two systems
of linear equations, then the two systems have the same
solutions set: solving one of the two systems is exactly the
same thing.
The GaussJordan algorithm
This is a process that starts with a given matrix A and
produces a matrix B in (reduced) rowechelon form,
which is rowequivalent to A. Reduced rowechelon form
is better, but rowechelon form is enough for almost all
purposes. If A is the augmented matrix of a system of
linear equations, then B will be a much simpler matrix
than A from which the consistency or inconsistency of
the corresponding system is immediately apparent and in fact the
complete solution of the system can be read off. As we want to
apply this process to the solution of linear systems we assume
that there are no zero rows in the original augmented matrix (a
zero row means a meaningless equation).
This process is made up of the following steps:

Step 1. Find the first
nonzero column moving from left to right (usually there are
no zero columns, otherwise the corresponding unknown is
useless, but it is better to consider this more general
case).

Step 2. By interchanging rows, if
necessary, ensure that the first entry in this column is
nonzero: this leading entry is the first pivot,
p_{1}_{.}

Step 3. Use the third elementary
row operation to obtain all zeros "under" this
pivot. You can proceed as follows: if the row number
i has a non zero entry, say a, under the
pivot, multiply the first row by and add it to row number i.

Step 4. Repeat the process to the
matrix you obtain by deleting row 1, until you obtain the
rowechelon form.

Step 5. If you are interested in
the reduced rowechelon form, divide each row by the pivot
and suitably use the third elementary row operation.
See an example.
Systematic solution of linear systems
Suppose a system of m linear equations in n
unknowns x_{1}, x_{2}, ...,
x_{n} has augmented matrix Ab. Via the
GaussJordan algorithm transform the matrix Ab in a
matrix Bc with B in rowechelon (or reduced
rowechelon) form. The number of pivots in the matrix B
is called the rank, r, of the system,
and we must have r≤min(m,n).
Once the augmented matrix is so reduced the consistency or
inconsistency of the system can immediately be checked:

The system is consistent if and only if in
correspondence to all zero rows (if any) in the matrix
B, the corresponding constants are zero.
Also the number of solutions can immediately be checked.

If r=n there is a unique solution, that can be
easily found if the system is in reduced rowechelon form.

If r<n there are infinitely many solutions: there
are columns without pivot and the corresponding unknowns can
take on arbitrary values and may be considered as
independent unknowns. The other unknowns
(dependent unknowns) are expressed in terms of the
independent ones. It's usual to say that there are
∞^{nr} solutions, to point
out the fact that exactly nr unknowns remain
completely unspecified.
See the examples.
If all constants are zero the system is called
homogeneous. A homogenous system is always consistent
as it has at least the trivial solution (0, 0, ... ,0). It also
has other non trivial solutions if m<n.
Homogeneous systems play an important role in the theory of
linear functions between vector spaces.
copyright 2000 et seq. maddalena falanga & luciano battaia
first published on march 15 2002  last updated on september 01
2003