Linear Algebra for Machine Learning Part 3 — System of Linear Equations

A system of linear equations (or linear system) is a collection of two or more linear equations involving the same set of variables.

Representation of linear equations in matrix and vector forms:

Solution set of linear equations :

Every linear system may have only one of three possible number of solutions:

1. The system has a single unique solution.
2. The system has infinitely many solutions.
3. The system has no solution.

Geometrical Representation :

For a system of two variables (x and y), each linear equation determines a line on the xy-plane. The solution set is the intersection of these lines, and is hence either a line, a single point or don’t have any common point.

Hyperplane: This is a very important term in machine learning and is used very frequently. Below is a good explanation of hyperplane from wikipedia —

A hyperplane is a subspace whose dimension is one less than that of its ambient space. If a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyperplanes are the 1-dimensional lines. This notion can be used in any general space in which the concept of the dimension of a subspace is defined.

Each linear equation determines a hyperplane in n-dimensional space where n is the number of variables. The solution set is the intersection of these hyperplanes.

Consistency : A linear system is said to be consistent if it has at least one solution and is said to be inconsistent if it has no solution.

Linear Independence : A linear system is said to be independent if none of the equations can be written as a linear combination of others. For example equations x+y = 2 and 2x+2y = 4 are not linearly independent as the 2nd equation can be obtain by multiplying 2 with the 1st equation.

Span: The span of a set of vectors is the set of points obtained by all linear combination of the set of vectors. For example the vector set{(1,0,0), (0,1,0), (0,0,1)} span all the real coordinate space of 3 dimension (R³). Any n number of linearly independent vectors with real numbers can span a real coordinate space of dimension n. Span of a given set of vectors can be determined by the linearly independent vectors in the set. This thread has a simple example about determining span of given vector set.

Rank of Matrix : The maximum number of linearly independent rows of a matrix is called the row rank, and the maximum number of linearly independent columns is called the column rank of the matrix.

For any matrix A, row rank of A = column rank of A = rank of A

Here and here are some good explanations of the above statement.

How to determine rank of matrix: Rank of matrix can be found by reducing the matrix in ‘Echelon Form’ s (Row Echelon Form or Reduced Row Echelon Form). This is done by elementary row operations and the whole method is called Gaussian Elimination or Gauss–Jordan elimination.

Row Echelon Form(ref) and Reduced Row Echelon Form (rref)

Matrix Rank and number of solutions: Now if we know the rank of Coefficient and Augmented matrices, then we can determine the number of solutions of a linear system of equations. Below is a diagram which will help you to understand the whole concept—

Solution methods of linear equations: There many different ways to solve a system of linear equation. Please read about the Gaussian Elimination (link)method and matrix inverse(link) method.

All parts in this series —

Part 1 — Building Blocks

Part 2 — Matrices

Part 3 — System of Linear Equations

Part 4 — Linear Transformation and Eigendecomposition(EVD)

Part 5 — Singular Value Decomposition (SVD) and Matrix Pseudoinverse

Part 6 — Dimensionality Reduction and PCA