Gaussian elimination, also known as row reduction, is converting a matrix into echelon form. This is done by applying elementary row operations to the matrix. You can go further and convert the matrix into reduced row echelon form (RREF), which is where the matrix is in echelon form, the first entry in each row is a 1 and each column with a leading entry has zeros in all other entries.
RREF is useful because it puts the matrix into a form where it will have the minimum number of variables in the solution. This is useful for solving systems of linear equations, and many other things that come later.
The elementary row operations are:
To begin, we start by trying to reduce the matrix to a form where the lower left corner is all zeros. This is done by adding multiples of the first row to the other rows to make the first column all zeros. Then we do the same for the second row, and so on.
For example, we can start with the matrix:
First, we want to make the first column all zeros. The first column (below the first row) has a 1, a 1 and a 3, so we want to multiply by -1/1 = -1 and -3/1 = -3 respectively, and add them to the second and third rows.
These row operations are expressed as L2 + -1 L1 → L2 and L3 + -3 L1 → L3. The L2 and L3 represent the rows, and the numbers represent what to multiply the rows by.
The result is:
Now we do the same with the second column. The second column (below the second row) has a -2 and a 2, so we want to multiply by -2/-2 = 1 respectively, and add it to the third row (L3 + 1 L2 → L3).
The result is:
This is now in echelon form because:
But we still have work to do to get it into RREF. We want to make the first entry of each row a 1, and all other entries in those columns zeros. We can do this by multiplying each row by the reciprocal of the first entry in that row, and then adding multiples of that row to the other rows to make the other entries in that column zeros.
Step 1: Multiply each row by the reciprocal of the first entry in that row.
Here that's -1/2 L2 → L2. The result is:
Step 2: Add multiples of rows to the other rows to make the other entries in that column zeros. Tip: start with the bottom row and work your way up.
Here that's L1 + -3L2 → L1. The result is:
This is now in RREF.
To do matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the second matrix. The result will have the same number of rows as the first matrix and the same number of columns as the second matrix.
Syntax of a matrix dimension m x n means m rows and n columns.
To remember this (m x n) * (n x p) = (m x p). Touching variables must be the same, and the result is plucked from the outside.
Now that you have this grid ready, go through each row of the first matrix and do a dot product with each column of the second matrix. The result is the entry in the result matrix at the same row and column as the two matrices you just multiplied.
An example:
First we do the dot product of the first row of the first matrix and the first column of the second matrix. This is 1 * -1 + 6 * 1 = -1 + 6 = 5. This is the first entry of the result matrix, at position (1, 1).
Next we do the dot product of the first row of the first matrix and the second column of the second matrix. This is 1 * 7 + 6 * 7 = 7 + 42 = 49. This is the second entry of the result matrix at position (1, 2).
Next we do the dot product of the second row of the first matrix and the first column of the second matrix. This is 3 * -1 + 1 * 1 = -3 + 1 = -2. This is the third entry of the result matrix at position (2, 1).
Finally we do the dot product of the second row of the first matrix and the second column of the second matrix. This is 3 * 7 + 1 * 7 = 21 + 7 = 28. This is the fourth entry of the result matrix at position (2, 2).
The result is:
Make sure to keep in mind that matrix multiplication is not commutative. A * B != B * A.
A matrix vector product is a special case of matrix multiplication where the vector is a matrix with only one column. The result is a vector with the same number of rows as the first matrix. ((m x n) * (n x 1) = (m x 1))
A matrix inverse is a matrix that when multiplied by the original matrix results in the identity matrix. (A * A-1 = I)
To find the inverse of a matrix, we use the Gauss-Jordan method. We start with the matrix we want to find the inverse of, and the identity matrix of the same size. We then do row operations on the matrix we want to find the inverse of until it is in RREF. We do the same row operations on the identity matrix. The result is the inverse of the original matrix.
RREF([ A I ]) = [ I A-1 ]. If there is no inverse, the result will not be the identity matrix.
A solution space is the set of all solutions to a system of linear equations. The solution space can be represented as a vector space.
Let's go back to the example from the Gaussian elimination section. After we put the matrix into RREF, we got:
This is the same as the system of equations:
x1 - 2x3 = -3
x2 + x3 = 4
0 = 0
Next solve for all the variables with a leading entry. In this case, x1 and x2 have leading entries, so we solve for them in terms of the other variables. Then add the free variables to the solution, in the form xn = xn. Example below:
x1 = -3 + 2x3
x2 = 4 - x3
x3 = 0 + x3
We can then write this as a vector equation:
We can see that the solution space is a vector space with a dimension of 1, and it's all offsets off the vector [ -3 4 0 ].
A determinant is the scaling factor of a matrix used as a transformation matrix. Also, the product of a matrix's eigenvalues.
To evaluate a determinant of a matrix greater than 2 x 2, we use the Laplace expansion. This is where we pick a row, and multiply each entry in that row or column by the determinant of the matrix formed by removing that row and column (cofactor). Then we add all of those together, alternating between adding and subtracting (add the first and subtract the second on odd numbered rows and subtract the first and add the second on even numbered rows).
A matrix's minors are the determinants of the matrices formed by removing a row and column.
Cramer's Rule solves a system of linear equations by using determinants. It is not efficient for large systems of equations, but it is useful for small systems of equations, especially when you need a formula for the solution.
The solution to a system of linear equations is:
xi = det(Ai) / det(A)
Where Ai is the matrix A with the ith column replaced with the solution vector.
Vectors are useful tools for representing many things in the real world that actually have a magnitude and direction. For example, velocity, acceleration, force, etc. However, vectors can also be used to represent things that don't have a magnitude and direction, such as a combination of two factors used for a linear regression.
The dot product of two vectors is the sum of the products of the corresponding entries. This is also equal to the magnitude of the first vector times the magnitude of the projection of the second vector onto the first vector times the cosine of the angle between the two vectors.
The dot product is useful for finding the angle between two vectors, and for finding the projection of one vector onto another.
The dot product is commutative, so A * B = B * A.
Furthermore, a * a = |a|2.
It is the orthogonal projection of a vector onto another vector. It gives the closest vector to the first vector that is parallel to the second vector.
The projection of a onto b, projb a = (a . b)/(b . b)*b
An abstraction of our current space. It is n dimensional, and is denoted ℝn.
A subspace is a subset of a vector space that is also a vector space. It must contain the zero vector, and be closed under addition and scalar multiplication.
Vectors are linearly independent if none of them can be written as a linear combination of the others. Use row reduction to determine if vectors are linearly independent, or just spot it if it's obvious. (If there are only two columns, it should be obvious.)
Row space is the span of the rows of a matrix. It is also the number of leading entries in the matrix after it is in RREF.
To find the basis of the row space, find the RREF of the matrix and take the rows that are nonzero as your basis.
The column space of a matrix is the span of the columns of a matrix. It is the same as the row space of the transpose of the matrix.
To find the basis of the column space, find the RREF of the matrix and take the columns from the original matrix that have leading entries in the row reduced form as your basis.
The rank of a matrix is the dimension of the column space of the matrix. It is also the number of pivots in the matrix after it is in RREF.
rank(A) + nullity(A) = n, where n is the number of columns in the matrix.
Col(A) = Row(AT)
The null space of a matrix is the set of all vectors that when multiplied by the matrix result in the zero vector. It is the same as the solution space of the homogeneous system of linear equations Ax = 0.
Orthogonal Basis:
v1 = u1
v2 = u2 - projv1 u2 = u2 - (u2 . v1)/(v1 . v1) * v1
v3 = u3 - projv1 u2 - projv2 u2
...
To get an orthonormal basis, divide each vector by its magnitude. You can do this while calculating or after.