System of linear equations

Generally, a system of linear equations can be represented compactly in the matrix form . Te product is a linear combination of the columns of .
The general approach to solving a system of linear equations is:

1. Find a particular solution to .
2. Find all solutions to .
3. Combine the solutions from steps 1 and 2 to form the general solution.

Elementary transformations

These help us transform the equation into a simpler form, and consist of:

• Exchange of two equations (rows in the matrix representing the system of equations)
• Multiplication of an equation (row) with a constant
• Addition of two equations (rows)
  The leading coefficient of a row (first nonzero number from the left) is called the pivot and is always strictly to the right of the pivot above it. Thus any equation system in row-echelon form always has a “staircase” structure.

Row echelon form

A matrix is row-echelon form if:

• all rows that contain only zeros are at the bottom of the matrix; and all rows that contain at least one nonzero element are on top of rows that contain only zeros.
• looking at nonzero rows only, the first nonzero number from the left, or the pivot, is always strictly to the right of the pivot above it.
  basic variables - variables corresponding to pivots in row-echelon form
  free variables - other variables that are not basic variables

ex. in the augmented matrix the basic variables are as these are exactly the columns that contain a leading/pivot entry in some row. The free variables are thus and . More reasoning: in row 1 the column corresponding to is the first non-zero, so it’s a pivot variable or a basic variable. In row 2 that’s while in row 4 that’s .

Reduced row echelon form

An equation system is said to be in reduced row echelon form if:

• it’s in row echelon form
• every pivot is 1 (only for the columns that have leading 1s)
• the pivot is the only non-zero entry in its column
  ex.

Gaussian elimination

Reducing the augmented matrix (which compactly represents the system of linear equations ) to reduced row echelon form using elementary transformations. (strictly speaking, that’s Gauss-Jordan elimination, but this is what was written in MML).
Rank of a matrix is the number of nonzero rows in REF, or the number of pivots in REF, or the number of linearly independent rows and columns in a matrix.
Some facts about the rank:

• The column rank equals the row rank, i.e.
• The columns of span a subspace with . This subspace will be called the image or range later. A basis of can be found by applying Gaussian elimination to to identify the pivot columns. See Vector Subspaces for more information.
• The rows of span a subspace with . A basis of can be found by applying Gaussian elimination to .
• For all it holds that is regular (invertible) if and only if.
• For all and all it holds that the linear equation system can be solved if and only if where denotes the augmented system.
• For the subspace solutions for possesses dimension . This subspace will be called the kernel or the null space.
• A matrix has a full rank if its rank equals the largest possible rank for a matrix of the same dimensions. This means that the rank of a full rank matrix is the lesser of the number of rows and columns, i.e. . A matrix is said to be rank deficient if it does not have full rank;.

General method of solving a linear equation

For a system where A is an m x n matrix (m equations, n unknowns),

1. Form the augmented matrix .
2. Row-reduce to echelon form. This gives you two ranks to compare:
   • rank(A) - number of pivot columns in then coefficient matrix
   • rank() - number of pivot columns in the augmented matrix. Let’s call this rank(B)
3. It follows that:
   • rank(A) < rank(B) - no solution
   • rank(A) = rank(B) = n - unique solution
   • rank(A) = rank(B) < n - infinitely many solutions

Particular and general solutions

The section for general solutions is currently missing.
For determining the particular solution, we take the augmented matrix in the row echelon form and look out for pivot columns. We then express the right hand side of the equation system using the pivot columns such that:

essentially, we are just putting all free variables as zero.
In practice it would look something like this:

Here
When we put everything together, we must not forget the non pivot columns for which we set the coefficients implicitly to 0. Therefore here the particular solution is: