Basics of Linear Algebra
Basics of Linear Algebra
1. Introduction
Linear Algebra is an essential branch of mathematics that deals with the study of linear equations and their representations in vector spaces. It is a fundamental concept in many areas, including physics, engineering, economics, and computer science. Linear Algebra involves the study of vectors, matrices, and linear spaces. In this blog post, we will discuss the basics of Linear Algebra.
2. Linear Spaces
2.1 Definition
Let F be a set of at least two numbers. If the four operations of addition, subtraction, multiplication, and division are closed on F, then F is called a number field.
Suppose there is a set V, where each element \(\{V_1,V_2,...\}\)is a vector. If these vectors satisfy additivity and scalar multiplication, then V is called a linear space over F.
A linear space is a collection of vectors that satisfies certain properties. A linear space is also called a vector space. It is a fundamental concept in Linear Algebra that allows us to generalize the properties of vectors to more abstract structures.The properties of vector addition and scalar multiplication are called axioms, and they define the properties of the linear space.
Note that the vector is a generalized concept. It can be a number, a vector, or a matrix. As long as these vectors satisfy the properties mentioned above, they can be called a linear space.
2.2 Base dimensional coordinates
Let \(V\) be a linear space. If there exists a non-empty subset \(B=\{\boldsymbol{v}_1,\boldsymbol{v}_2,\cdots,\boldsymbol{v}_n\}\subset V\) that satisfies the following two conditions:
- \(B\) is linearly independent.
- Any vector \(\boldsymbol{v}\) in \(V\) can be expressed as a linear combination of the vectors in \(B\), i.e., \(\boldsymbol{v}=a_1\boldsymbol{v}_1+a_2\boldsymbol{v}_2+\cdots+a_n\boldsymbol{v}_n\).
Then \(B\) is called a basis of \(V\), and \(n\) is called the dimension of \(V\), denoted as \(dim(V)=n\). \(a = \{a_1,a_2,...a_n\}\) is called the coordinate of vector v.
To check if a set of vectors is a basis, put them into a matrix and find the determinant. If the determinant is equal to 0, then the set of vectors is a basis. Specifically, if the mode of all basis vector are 1, then this basis is called a Orthonormal basis.
**********************Coordinate**********************
The coefficients of the basis vectors form the coordinates of the vector with respect to the basis. Note that a basis for a linear space is not always unique, thus different basis selection lead to different coordinate. Suppose two basis \(\alpha, \beta\), respectively give two coordinate \((a_1,a_2,...a_n),(b_1,b_2,...b_n)\) to a vector v. Let \(\gamma\) be a basis equals \(\alpha+\beta\), then \(\gamma\) would give v a coordinate such that \((a_1+b_1,a_2+b_2,...a_n+b_n)\)
3. Vector
A vector is a mathematical entity that represents a quantity with magnitude and direction. In Linear Algebra, vectors are represented as an ordered list of numbers. For example, a two-dimensional vector can be represented as (x, y). Vectors can be added and subtracted, and multiplied by scalars to produce new vectors. The magnitude of a vector is the length of the vector, and it is calculated using the Pythagorean theorem.
3.1 Vector Operations
To add or subtract two vectors, the dimensions of the two vectors must be the same, and then the corresponding components must be added.
\[ (a_1,a_2,..a_n)+(b_1,b_2,...b_n) = (a_1+b_1,a_2+b_2,...a_n+b_n) \]
Scalar multiplication of a vector:
\[ k(a_1,a_2,...a_n) = (ka_1,ka_2,...ka_n) \]
3.2 Linear Relationships of Vectors
Suppose \(\beta,\alpha_1,\alpha_2,...\alpha_n\) are all m-dimensional vectors. If there exist \((k_1,k_2,...k_n)\) such that \(\beta = k_1a_2+k_2a_2+...k_na_n\) holds true, then \(\beta\) is called a linear combination of \((\alpha_1,\alpha_2,...\alpha_n)\), i.e., there exists:
\[ \left\{ \begin{aligned} \beta_1 &= k_1a_{11}+k_2a_{21}+...k_na_{n1}\\ ...\\ \beta_n &= k_1a_{1n}+k_2a_{2n}+...k_na_{nn} \end{aligned}\right. \]
Let \(\alpha_1,\alpha_2,...\alpha_n\) denote a set of m-dimensional vectors. If there exists a set of coefficient that are not all zero \((k_1,k_2,...k_n)\), then \(\alpha_1,\alpha_2,...\alpha_n\) is call linearly correlated. Otherwise, it is called linearly uncorrelated. If n > m, then \(\alpha_1,\alpha_2,...\alpha_n\) has to be linearly correlated
If \(\alpha_1,\alpha_2,...\alpha_n\) is linear correlated, then at least one vector in it can be linearly expressed by other vectors
3.3 The Rank of Vector
Let \(\alpha_1,\alpha_2,...\alpha_n\) denote a set of m-dimensional vectors. Suppose a subset with r vectors, \(\alpha_1,..\alpha_r\), satisfies:
- \(\alpha_1,..\alpha_r\) is linearly uncorrelated
- Any subsets with \(r+ 1\) vectors will be linearly correlated
- Every vector in \(\alpha_1,\alpha_2,...\alpha_n\) can be linearly expressed in \(\alpha_1,..\alpha_r\)
Then we call \(\alpha_1,..\alpha_k\) a Maximal linearly independent set. r is called the rank of the set of vectors. Rank actually represents the number of dimension of basis in a linear space. The range of rank is \([0,m]\).
Notice that, no matter you treat \(\alpha_i\) as a row vector, column vector or treat \(\alpha_1,\alpha_2,...\alpha_n\) as matrix, the rank is the same. This indicates that, if you want to find out the rank of a group of vectors(e.g. sample value of features), then you can calculate the rank of matrix consists of these vectors
4. Matrix
A matrix is a rectangular array of numbers arranged in rows and columns. Matrices have many applications, including solving systems of linear equations and representing linear transformations. In Linear Algebra, matrices are used to represent linear transformations of vectors.
Identity Matrix
If all the elements on the diagonal of a matrix are 1, and all the other elements are 0, then this matrix is called an identity matrix, denoted as \(I\).
\[ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \]
For matrix \(A_{n\times m }\)
\[ I_nA = A \]
\[ AI_M = A \]
Diagonal Matrix
A diagonal matrix is a square matrix in which all the off-diagonal elements are zero. The diagonal elements can be any number, including zero.
\[ \begin{bmatrix} \lambda_1 & 0 & 0 \\ 0 & \lambda_2 & 0 \\ 0 & 0 & \lambda_3 \\ \end{bmatrix} \]
The determinant of a diagonal matrix is the product of its diagonal elements.
\[ |D|= \prod_i^n\lambda_n \]
Symmetric Matrix
A symmetric matrix is a square matrix where the transpose of the matrix is equal to the matrix itself. In other words, a matrix A is symmetric if and only if \(A^T = A\).
\[ \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 0 \\ 3 & 0 & 5 \\ \end{bmatrix} \]
Unitary Matrix
A unitary matrix is a square matrix whose conjugate transpose is its inverse. In real number domain, this equals that \(U^T = U^ {-1}\)
4.1 Determinant
The determinant of a square matrix is a scalar value that can be calculated from the elements of the matrix. It is denoted by \(|A|\) or \(det(A )\). For a \(n \times n\) matrix A, let \(j = (j_1,j_2,...j_n)\) denote a possible permutation of the column label:
$$ det( \[\begin{bmatrix} a_{11} & ... & a_{1n}\\ ... & ... &...\\ a_{n1} & ... & a_{nn}\\ \end{bmatrix}\]) = j (-1)^{N(j )}a{j_1}a_{j_2}...a_{j_n} $$
where \(N(j)\) is the inversion number(number of inverse sub permutation in \(j\)).
For a square matrix A, its determinant has following properties:
- \(|A| = |A^T|\)
- If a row of a determinant has a common factor, it can be factored out of the determinant.
) $$
- If there are two rows in a matrix that are proportional, the determinant of the matrix is 0.
4.2 Matrix Operations
Addition and Subtraction(only applied on same shape): \[ \begin{bmatrix} a_ 1 & a_ 2 \\ a_3 & a_4\\ \end{bmatrix} + \begin{bmatrix} b_ 1 & b_2 \\ b_3 & b_4\\ \end{bmatrix} = \begin{bmatrix} a_1+b_1 & a_2+b_2 \\ a_3 +b_3& a_4+b_4\\ \end{bmatrix} \]
Scalar multiplication
\[ k \begin{bmatrix} a_ 1 & a_ 2 \\ a_3 & a_4\\ \end{bmatrix} = \begin{bmatrix} ka_1 & ka_ 2 \\ ka_3 &k a_4\\ \end{bmatrix} \]
Multiplication(inner product, (n,m) x (m,k))
\(\begin{bmatrix} a_ 1 & a_ 2 \\ a_3 & a_4\\ \end{bmatrix} * \begin{bmatrix} b_ 1 & b_2 & b_3 \\ b_4 & b_5 & b_6\\ \end{bmatrix} = \begin{bmatrix} a_1*b_1 + a_2*b_4 & a_1*b_2+ a_2*b_ 5 & a_ 1*b_ 3+a_ 2*b_6 \\ a_3*b_1 + a_4*b_4 & a_3*b_2+ a_4*b_ 5 & a_3*b_3+a_4*b_6 \\ \end{bmatrix}\)
Note that for matrix multiplication, we may find:
- \(AB \ne BA\)
- \(AB = 0 \nrightarrow A=0 \ or \ B =0\)
- \(AB = AC, A \ne 0 \nrightarrow B = C\)
- \(A(BC) = (AB)C\)
- \((A+B)C = AB + BC\)
- \(C(A+B) = CA + CB\)
- \(k(AB) = (kA)B = A(kB) \quad k \ is \ constant\)
Power \[ A^k = A \cdot A \cdot A. ... A \]
\[ A^0 = I \]
\[ (AB)^k\ne A^KB^K \]
Transpose
\[ （A+B）^T = A^T + B^T \]
\[ (ABC)^T = C^TB^TA^T \]
4.3 Inverse of Matrix
The inverse of a square matrix A is another square matrix \(A^{-1}\) such that \(A \cdot A^{-1} = A \cdot A^{-1} = I\), where I is the identity matrix. Not all matrices have an inverse, and those that do not are called singular or non-invertible matrices. The inverse is a useful tool in solving systems of linear equations and in representing linear transformations.
$$ \[\begin{aligned} AB &= DC \\ A &= ABB^{-1} = DCB^{-1}\\ \end{aligned}\]$$
For an n x n matrix \(A\), \(A\) is invertible if and only if the determinant of \(A\) is not equal to 0, i.e. \(det(A) \neq 0\). For an invertible matrix \(A\), we can find its inverse matrix by using the Gaussian-Jordan elimination method or the adjugate matrix method.
In addition, if a matrix is a symmetric matrix, i.e. \(A^T = A\), then it is always an invertible matrix.
4.4 The Rank of Matrix
The rank of a matrix is the number of dimensions of the basis in a linear space. It indicates the degree of the transformation of the matrix. The range of the rank is \([0,m]\), where m is \(min(n_{row},n_{col})\). To find out the rank of a group of vectors, you can calculate the rank of the matrix consisting of these vectors. Note that rank of a matrix would be 0 if and only if the matrix is a zero matrix.
4.5 Eigenvalue and Eigenvector
Let A denote a n x n square matrix. For a number \(\lambda\) , if there exists a non-zero vector \(\alpha\) that \(A \alpha = \lambda \alpha\). Then we call \(\lambda\) a eigenvalue of A, \(\alpha\) a eigenvector of A. We know that in linear algebraic, a matrix can be taken as a linear transformation for a vector. That is two say, for a vector \(\alpha\) , if matrix A only scale \(\alpha\) without spinning it. then \(\alpha\) is the eigenvector, the scaling coefficient \(\lambda\) is the eigenvalue. In addition, if \(\alpha\) is a eigenvector of A, then any scalar multiplication \(C \alpha\) is also a eigenvector. One eigenvalue can correspond to multiple proportional eigenvectors, but conversely, one eigenvector will only correspond to one eigenvalue.
To find the eigenvalue of A:
\[ \begin{aligned} \lambda\alpha - A \alpha &= 0\\ (\lambda I - A)\alpha & =0 \\ \end{aligned} \]
To ensure this equation has at least one root, \(|\lambda I - A| = 0\). This equation is called the eigenfunction. With \(\lambda\) obtained, we can find \(\alpha\) by solving the equation \((\lambda I - A)\alpha =0\)
4.6 Decomposition of Matrix
Eigenvalue Decomposition
An \(n \times n\) matrix \(A\) is diagonalizable if and only if it has \(n\) linearly independent eigenvectors, this would ensure all eigenvalues of \(A\) are distinct. In this case, the eigenvectors of A can be used as a basis for A, and A can be expressed in the form \(A = PDP^{-1}\), where \(P\) is a matrix composed of the eigenvectors of \(A\), and \(D\) is a diagonal matrix composed of the eigenvalues of \(A\). We call these process a eigenvalue decomposition.
Especially, if A is an \(n \times n\) real symmetric matrix, then A must have n linearly independent eigenvectors, and it can be proved that these vectors are mutually orthogonal. In other words, these eigenvectors form an orthonormal basis for A. At this point, A can be decomposed into \(QDQ^{-1}\), where Q is an orthogonal matrix composed of A's eigenvectors. Each column represents a eigenvector and these vectors can be normalized. If Q is normalized, which means it is a standard orthogonal basis of A, then we have \(QQ^T = 1, Q^T = Q^{-1}\)
Singular Value Decomposition(SVD)
According to the necessary condition for matrix eigenvalue decomposition, non-square matrices cannot be decomposed into eigenvalues. To solve this problem, let A denote a \(n \times m\) matrix. We first conduct a eigenvalue decomposition on \(AA^T\)to obtain its matrix of eigenvectors \(U\), where \(U\) is a \(n \times n\) matrix. Then we repeat on \(A^T A\) and obtain \(V_{m \times m }\). It can be deduced that:
\[ A_{n \times m} = U_{n \times n} \Sigma_{n \times m} V_{m \times m}^T \]
where \(\Sigma\) is A matrix where all elements except those on the main diagonal are 0：
\[ \begin{bmatrix} \sigma_1 & 0 & 0 \\ 0 & \sigma_2 & 0 \\ 0 & 0 & \sigma_3 \\ 0 & 0 & 0 \\ 0 & 0 & 0\\ \end{bmatrix} \]
and U and V are both unitary matrices. This yields:
\[ A_{n \times m} V_{m \times m} = U_{n \times n} \Sigma_{n \times m} \]
Such a equation suggests that, for a m-dimension feature space, suppose V is a group of orthogonal basis, if we applied a linear transformation \(A_{m \times n}\) to map the basis into a n-dimension space, the results will still be a group of orthogonal basis, where \(U_{n \times n}\) is the standardization of the basis, and \(\Sigma\) gives the mode of each basis vector.
5. Systems of Linear Equations
A system of linear equations is a set of equations that can be represented as a matrix equation. Each row of the matrix represents an equation, and each column represents a variable. The system can be solved by finding the inverse of the matrix and multiplying it by the matrix of constants. Linear Algebra provides efficient methods to solve systems of linear equations, including Gauss-Jordan elimination, LU decomposition, and the inverse matrix method.