Linear_Algebra

This repository is written and practiced while studying linear algebra.
What is Linearity
Learning resource
- Lectures
  - Linear Algebra for Artificial Intelligence, Prof. Jaegul Choo (주재걸), Korea University - https://www.boostcourse.org/ai251
  - Linear Algebra 1, Prof. 하길찬, Sejong University - http://www.kocw.net/home/cview.do?cid=f41a378321625410
- Books
  - Lay et al. Linear Algebra and Its Applications, 5th edition, 2015
  - Howard Anton. Elementary Linear Algebra, 12th edition (Korean edition, Hanti Edu)
  - Mike X Cohen. Practical Linear Algebra for Data Science (Korean edition)
Current modified: 02/19/2024 Mon.

Scalar: a single number, e.g., 3.8
Vector (v): an ordered array. It is normally written as a column vector and denoted by a bold lowercase letter ↔ something without an order is a set
- Geometric interpretation: a line with a specific length (magnitude) and direction (angle)
- Dimensionality of a vector: the number of elements the vector has
  - e. g., R²: a vector with two elements
    - x = [x1, x2] or x = [x1, x2]ᵀ
  - e. g., R³: a vector with three elements
    - x = [x1, x2, x3] or x = [x1, x2, x3]ᵀ
  - R⁰: the zero-dimensional subspace (dimension = 0)
  - Rⁿ: n-dimensional space (dimension = n)
  - n-dimensional vector: a vector with n elements = an n-tuple
- Orientation of a vector: whether the vector runs along a column or along a row (an n-dimensional vector is normally written as a column vector)
  - Column vector: a vector formed from the values of each column of a matrix ~ writing a row vector vertically gives a column vector
    - "Column" carries the sense of a pillar, so picturing something vertical keeps rows and columns from being confused
  - Row vector: a vector formed from the values of each row of a matrix, e.g., [1, 2, 3, 4]
    - A row vector is normally written using a transpose. Transpose of x (= xᵀ)
- Zero vector: a vector whose elements are all 0, denoted by 0
- Practice
```
  If x = [ [1], [4], [5], [6] ], then x is a 4-dimensional column vector, x ∈ R⁴
  If y = [ [.3], [-7] ], then y is a 2-dimensional column vector, y ∈ R²
  If z = [ [1, 4, 5, 6] ], then z is a 4-dimensional row vector, z ∈ R⁴
  * Note that x and z hold the same elements in the same order but are different vectors, because their orientation differs
```

Addition is head-to-tail, subtraction is the arrow between two vectors, and the third panel is the one that matters: the projection coefficient beta = a'b / a'a, with the orthogonality of the residual checked numerically in the caption. Every least-squares result later in these notes is that panel repeated in higher dimensions.
Matrix (M): a two-dimensional array of numbers (a vector lifted one dimension higher), denoted by a bold uppercase letter
- In data science a matrix is regarded as a data table whose rows hold observations and whose columns hold features
- Size of a matrix: 3x2 (3 by 2) means a matrix made of 3 rows and 2 columns
Matrix notation
- A(n x n): square matrix, a matrix whose number of rows equals its number of columns (#rows = #columns)
- A(m x n): rectangular matrix, a matrix that is not square, i.e. its number of rows differs from its number of columns
- Aᵀ: the transpose of a vector or matrix, rotating the matrix about its main diagonal ~ that is, exchanging rows and columns (a(i,j)ᵀ = a(j,i))
  - For a vector, it converts a column vector into a row vector or a row vector into a column vector
  - Important! Transposing a vector or matrix twice returns the original vector or matrix. (Aᵀ)ᵀ = A
    - It looks obvious, but it becomes the key justification in important proofs in AI.
    - LIVE EVIL (order of operations)
      - (LIVE) = EᵀVᵀIᵀLᵀ
        
        The order when transposing a product of several matrices. The same rule applies not only to four matrices as above but to any number of them
- Aij: the element in the i-th row and j-th column
- Ai,: - the i-th row vector
- A:,j - the j-th column vector
Special matrices
- Random number matrix: a matrix whose numbers are drawn at random from a Gaussian (normal) distribution or similar (useful when studying linear algebra through code, because a matrix of any size and rank can be generated easily and quickly)
- Square matrix and nonsquare matrix
  - Square matrix: a matrix whose number of rows equals its number of columns, i.e. an R(N*N) matrix
  - Nonsquare matrix: a matrix whose number of rows differs from its number of columns. #rows > #columns is described as "tall", #rows < #columns as "wide"
- Diagonal matrix
  - A matrix whose off-diagonal elements are all 0, while the diagonal elements may be zero or nonzero (NumPy's diag() function)
    - The diagonal of a matrix is the set of elements running diagonally from the top left down to the bottom right
- Triangular matrix
  - A matrix in which everything above or everything below the main diagonal is 0 (NumPy's triu() extracts the upper triangular matrix, tril() the lower triangular matrix)
  - Upper triangular matrix: a matrix whose nonzero elements lie above the diagonal
  - Lower triangular matrix: a matrix whose nonzero elements lie below the diagonal
- Unit matrix
  - The most important matrix: a square diagonal matrix whose diagonal elements are all 1, denoted by the capital letter I (created with NumPy's eye() function)
    - It is the equivalent of the number 1, in the sense that multiplying a matrix or vector by the unit matrix returns the same matrix or vector
- Zero matrix
  - Analogous to the zero vector, a matrix whose elements are all 0, written in bold as 0 (created with NumPy's zeros() function)
- Symmetric matrix
  - A matrix identical to its own transpose (A = Aᵀ, possible only for a square matrix)
    - It tends to be numerically stable, which makes it convenient in computer algorithms, and it has many properties convenient for various operations
- Multiplicative method (creating a symmetric matrix from a nonsymmetric one)
  - Multiplying any matrix (nonsquare or nonsymmetric) by its own transpose produces a square symmetric matrix (AᵀA or AAᵀ)
  - Note, however, that AᵀA and AAᵀ are not the same matrix!
  - Proof
    - Squareness: if A has size M x N, then AᵀA is (N x M)(M x N), hence N x N; conversely AAᵀ is (M x N)(N x M), hence a matrix of size M x M
    - Symmetry: (AᵀA)ᵀ = AᵀAᵀᵀ = AᵀA, or (AAᵀ)ᵀ = AᵀᵀAᵀ = AAᵀ

The same grid under five matrices. Rotation preserves area (det = 1), the diagonal matrix scales it by the product of its entries, and the shear preserves it despite visibly distorting the grid. The last matrix has det = 0: the entire plane collapses onto a line, which is what rank deficiency looks like and why such a matrix has no inverse.
Addition and multiplication of vectors and matrices
- Addition is possible only between vectors of the same dimension, and is carried out by summing corresponding elements
- Geometric interpretation of vector addition and subtraction: the triangle rule and the parallelogram rule
  - Vector subtraction in particular is a very important concept, since it is the basis of orthogonal vector decomposition and of linear least squares
- Shifting a matrix - applied as a mechanism for finding the eigenvalues of a matrix and for regularizing a matrix
  - Implemented by adding a scalar to a square matrix, in the form of multiplying the unit matrix by a scalar and adding it
```
  A = np.array([ [4, 5, 1], [0, 1, 11], [4, 9, 7] ])
  s = 6
  A + s * np.eye(len(A))
```
  - In data science a relatively small shift is applied, so as to improve the numerical stability of the matrix while preserving as much of its information as possible along with the effect of the shift
- Scalar multiplication is also possible (very simple: multiply each element of the vector or matrix by the scalar). Denoted by α, β, λ, ... ~ e. g., λw = [36, 16, 4] (λ = 4, w = [9, 4, 1].T)
  - Geometric interpretation of scalar-vector multiplication (an important interpretation for matrix spaces, eigenvectors and singular vectors)
    - It rescales the magnitude without changing the direction of the vector
      - but, when the scalar is negative the vector flips (= a rotated vector). A rotated vector still points along the same infinite line, so the direction has not been changed
- Trace of a matrix
  - The sum of the diagonal elements (defined only for square matrices), denoted by tr(A)
  - Property: the trace of a matrix equals the sum of its eigenvalues (which in the end makes it a measure of the "volume" of the matrix's eigenspace)
Standard matrix multiplication - called standard matrix multiplication to distinguish it from other matrix products (e.g., the Hadamard product)
- Matrix multiplication: a matrix that stores the linear relationships for every pair between the rows of the left matrix and the columns of the right matrix
- Rules on the validity of matrix multiplication
  - It is valid only when the "inner" dimensions match, and the size of the product matrix is defined by the "outer" dimensions
    - Why it is valid only when the inner dimensions match: because the (i, j)-th element of the product matrix is the dot product between the i-th row of the left matrix and the j-th column of the right matrix
      - Dot product: a number that encodes the relationship between two vectors
  - e.g., given a matrix A of size 3x2 and a matrix B of size 2x2, the product AB produces a matrix of size 3x2
    - Here, the multiplication is possible only when the number of columns of the leading matrix equals the number of rows of the trailing matrix
    - If a matrix A of size 2x3 is multiplied by a matrix B of size 2x2 (AB), the operation is impossible because the sizes do not match
    - Also, AB and BA are entirely different operations, which shows that the commutative law does not hold (NOT commutative)
    - There are cases where both AB and BA can be computed, such as multiplying two square matrices of the same size, but even then the results are generally not equal
  - Practice
    - - The operation is impossible when the dimensions do not match, but NumPy has broadcasting, which makes addition of a row vector and a column vector possible
Matrix-vector multiplication
- It follows the same mechanism as standard matrix multiplication, and the result of a matrix-vector multiplication is always a vector. Used in many places including data science and machine learning
- Matrix-vector multiplication is the basis of matrix spaces
- Only a column vector, not a row vector, can be multiplied on the right of a matrix, and only a row vector, not a column vector, can be multiplied on the left of a matrix
- Multiplying a matrix by a row vector produces a row vector, and multiplying it by a column vector produces a column vector
  - That is, Av and vᵀA are valid, but Avᵀ and vA are not (a row vector only on the left, a column vector only on the right)
    - A matrix of size MxN cannot be multiplied by a row vector of size 1xM, but multiplying a row vector of size 1xM by a matrix of size MxN gives a row vector of size 1xN as the result
    - Conversely, multiplying a matrix of size MxN by a column vector of size Nx1 gives a column vector of size Mx1 and is therefore valid, whereas multiplying a column vector of size Nx1 by a matrix of size MxN is impossible
- Two concrete interpretations of matrix-vector multiplication
  1. Linear weighted combination
    - Putting each vector into the matrix, putting the weights into the elements of the vector, and multiplying
  2. Geometric transformation
    - Matrix-vector multiplication acts to rotate and scale the vector concerned
Norm and Unit vector
- Norm of a vector (its geometric length): the distance from the tail of the vector to its head. Denoted by || v ||
  - Normally obtained with the standard Euclidean distance formula (L2 norm)
- Unit vector: a vector of geometric length 1, || v || = 1
  - Used for orthogonal and rotation matrices, eigenvectors and singular vectors
  - Creating a unit vector (normalizing a vector): dividing a vector by its norm produces a unit vector (v^).
Dot product (scalar product) of vectors, the single most important operation in all of linear algebra
- The basis of many operations and algorithms including convolution, correlation, the Fourier transform, matrix multiplication, linear feature extraction and signal filtering
- Denoted by vᵀw (otherwise, v·w or < v, w >)
- - Multiply corresponding elements of the two vectors and then add all the results (that is, multiply element-wise and sum)
    - It holds only between two vectors of the same dimension
- Practice
  - [1 2 3 4]·[5 6 7 8] = 5 + 12 + 21 + 32 = 70
  - An interesting property of the dot product: multiplying a vector by a scalar scales the dot product by the same amount (s*v = σvᵀw); multiplying by a negative scalar reverses the sign, and multiplying by zero makes the dot product zero as well
- In other words, the dot product can be interpreted as a measure of the similarity, or of the mapping, between two vectors
  - ex: if the heights and weights of 20 people were collected and stored in two vectors, the two variables could be expected to be related to each other (taller people tend to be heavier)
    - So when they are related as above, the dot product of the two vectors will be large
    - However, the dot product of data measured in grams (g) and centimetres (cm) is larger than that of data measured in kilograms (kg) and metres (m), because of the difference in units.
      - This difference in units can be removed with a normalization factor
- The normalized dot product between two variables: the Pearson correlation coefficient
- Distributive law of the dot product
  - aᵀ(b+c) = aᵀb + aᵀc
- Geometric interpretation of the dot product: the product of the norms (magnitudes) of the two vectors, scaled by the cosine of the angle between them
  - α = cos(θv, w) ||v|| ||w||, (-1 <= cos(θv, w) <= +1)
  - Memorize: the dot product of orthogonal vectors is 0. (The three statements below all say the same thing; read them repeatedly and memorize them)
    - The two vectors are orthogonal.
    - The dot product of the two vectors is 0.
    - The angle between the two vectors is 90°.

Sweeping w through a full turn and plotting v.w traces a cosine. It is positive when the vectors point the same way, exactly zero at 90 and 270 degrees, and negative when they oppose. The zero crossing is the whole content of "orthogonal vectors have dot product 0", and the fact that the curve is a scaled cosine is why the dot product normalizes into a correlation coefficient.
Other vector products
- Hadamard product
  - A method of multiplying corresponding elements of two vectors of the same dimension ~ the result of the product is a vector of the same dimension
    - Convenient when multiplying several scalars together
- Outer product: a rank-1 matrix
  - Builds a matrix from a column vector and a row vector. Denoted by vwᵀ
  - - Each row of the outer product matrix is the row-vector scalar multiplied by the corresponding column-vector element
    - Each column of the outer product matrix is the column-vector scalar multiplied by the corresponding row-vector element
Orthogonal vector decomposition
- "Decomposing" a vector or matrix splits it into several simpler pieces
  - Used to reveal hidden information, to put a matrix into a form that is easier to work with, or to compress data
  - Directly connected to the Gram-Schmidt process and QR decomposition
- Orthogonal projection = minimum-distance projection ~ essential groundwork for learning vector decomposition
  - Given two vectors a and b in standard position, the point on a closest to the head of b must be found
  - That is, vector b is projected onto vector a so that the projection distance is minimized. That point is βa, a shortened version of a
  - The important part is that the line from b to βa can be defined through vector subtraction
  - b-βa is orthogonal to βa = these vectors are perpendicular. That is, the dot product between the two vectors is 0
    - aᵀ(b - βa) = 0
      1. aᵀb - βaᵀa=0 (distributive law of the dot product)
      2. βaᵀa = aᵀb
      3. ∴ β = aᵀb / aᵀa
  - Orthogonal projection: β = aᵀb / aᵀa
    - It becomes the foundation of many fields including least squares, statistics and machine learning
- Orthogonal vector decomposition: given a "target vector" t and a "reference vector" r, decomposing the target vector into two different vectors such that
  1. the sum of the two vectors is the target vector
  2. one vector is orthogonal to the reference vector while the other is parallel to it
  - The two vectors formed from the target vector are the perpendicular component t⊥r and the parallel component t||r
  1. How to find the parallel component t||r: the vector parallel to r is the projection of t onto r
    - t||r = r(tᵀr / rᵀr)
  2. How to find the perpendicular component t⊥r: subtract the parallel component t||r from the target vector t (using the fact that the sum of the two components is the target vector)
  - t = t⊥r + t||r
  - ∴ t⊥r = t - t||r
Other rules
- A(B + C) = AB + AC: the distributive law holds.
- A(BC) = (AB)C: the associative law holds.
- (AB)ᵀ = BᵀAᵀ: transposing AB reverses the order of A and B.
- (AB)^-1 = B^-1A^-1: as with the transpose, the inverse of AB reverses the order.

2. Linear System

Linear equation: given unknowns x1, x2, ..., xn, an equation for solving for the unknowns, written as a1x1 + a2x2 + ... + anxn = b.
- In linear algebra this notation is written concisely as aᵀx = b.
- a1, a2, ..., an are called coefficients; they are real or complex numbers and are generally already known.
- b is called the constant.
- An equation containing one unknown or a set of unknowns such as x1, x2, ..., xn is called a linear system.
Linear systems are used in machine learning when the weights for target data are to be obtained from input data.
- e.g., used when a lifespan is to be obtained from a person's height (x1), weight (x2) and smoking status (x3)
- 60x1 + 5.5x2 + 1x3 = 66
- 65x1 + 5.0x2 + 0x3 = 74
- 55x1 + 6.0x2 + 1x3 = 78
- A system of equations such as the above can be written as Ax = b, with the matrix A collecting the coefficients, the column vector x the unknowns, and the column vector b the constants.
- To find x in Ax = b, take the inverse of A and multiply both sides by it. Since AA^-1 = I (the identity matrix), x can be obtained as x = bA^-1.
Identity matrix
- The identity matrix means a square matrix whose diagonal elements are all 1 and whose remaining elements are all 0.
- True to its name, the identity matrix I returns A whenever it is multiplied by any matrix A. xIn = x
Inverse matrix - the master key of matrix equations
- The inverse exists only for square matrices.
  - For a rectangular matrix, an approximation can be computed by methods such as row reduction (further study: Book Chap 1.2, 1.5)
- AA^-1 = A^-1A = In
  - The inverse always yields the identity matrix regardless of which side of the original matrix it is multiplied on.
- How to solve a linear system through the inverse: find the inverse and multiply it by the constant vector b to obtain the solution!
  - 1. Ax = b
    2. A^-1Ax = A^-1b
    3. Inx = A^-1b
    4. x = A^-1b
- The inverse of a 2x2 matrix can be found quickly with a formula. For inverses larger than this, Gaussian elimination can be used to find the inverse quickly
Determinant
- The determinant is the expression that decides whether a matrix is invertible or non-invertible. For example, for a 2x2 matrix A, det A = bc-ad.
- If det A ≠ 0 then A is said to be invertible, and if det A = 0 it is said to be non-invertible.
- If a matrix A is invertible, its solution is always uniquely obtained - that is, there is exactly one solution.
- If a matrix is non-invertible, there are either infinitely many solutions or no solution.
  - Infinitely many solutions (under-determined system): the ratios of the coefficients are the same and the constants are also the same, giving something like 0x + 0y = 0
    - In machine-learning terms, the case where there are more features (unknowns) than data (equations) - fewer equations than unknowns
  - No solution (over-determined system): the ratios of the coefficients are the same but the constants differ, giving something like 0x + 0y = 2
    - In machine-learning terms, the case where there are more data (equations) than features (unknowns) - more equations than unknowns
- Further learning resources
  - https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-18-properties-of-determinants/
  - https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/resources/lecture-19-determinant-formulas-and-cofactors/

3. Linear combination, vector equation, Four views of matrix multiplication

Vector space: a collection of vectors. (A finite or infinite number of vectors may exist) Denoted by V = { v1, ..., vn }
Linear combination: a way of mixing information by giving a different weight to each of several variables
- w = λ1v1 + λ2v2 + ... + λnvn (that is, multiplying vectors by scalars and then summing the values is called a linear combination)
- Linearly dependent: a vector set V is called linearly dependent when at least one vector in the set can be written as a linear combination of the other vectors in the set
- Applications of linear combination
  1. Data predicted from a statistical model is generated as a linear combination of the regressors (independent variables) and the coefficients (scalars) computed through a least squares algorithm
  2. In dimensionality reduction (e.g., principal component analysis), each component (factor or mode) is derived as a linear combination of the data channels and the weights (coefficients) that maximize the variance of the component
  3. An artificial neural network (ANN) has two operations: a linear combination of the input data and a nonlinear transformation. The weights (w) are learned so as to minimize the loss function
    - Loss function: the difference between the model prediction and the actual target variable
Vector equation
Four views of matrix multiplication

4. Linear independence, span, and subspace

Linearly independent: a vector set is called "linearly independent" when no vector in the set can be written as a linear combination of the vectors in the set ↔ linearly dependent
- In the case above there are few enough vectors in the set that whether they can be written as linear multiples, and hence whether the set is linearly dependent or independent, can be judged easily by eye alone. But what about a far more complicated vector set such as the one below?
  - - The way to determine linear independence is to build a matrix from the vector set, compute the rank of the matrix, and compare it with the smaller of the number of rows and the number of columns. This will be studied and written up later
- Linear independence in mathematics: a vector set is linearly independent if there is no way to combine the vectors linearly so as to produce the zero vector
  - Mathematical definition of linear dependence
    - 0 = λ1v1 + λ2v2 + ... + λnvn, λ ∈ R, λ1 ≠ 0
    - λ1 ≠ 0 and a nontrivial solution exists. That is, if a vector set is linearly dependent, the zero vector can be produced by a linear combination.
- If columns are dependent, rows are dependent too.
Subspace: the space made by taking the vectors of a (finite) vector set and combining them linearly in infinitely many ways with many different weights (the result generated by the vector set)
- The dimension of the subspace generated by a vector set is the minimum number of vectors needed to form a linearly independent set
- When the vector set is linearly independent: dimension of the subspace = number of vectors in the set
- When the vector set is linearly dependent: dimension of the subspace < number of vectors in the set
Span: the mechanism that forms all possible linear combinations
Basis: the set of references used to describe the information (e.g., data) in a matrix. That is, it represents the minimum set of vectors needed to generate a vector space (much like the blocks used to put up a building in Minecraft)
- The basis is extremely important in data science and machine learning (because every analysis is essentially aimed at finding the optimal basis vectors for a particular problem)
- The most common basis set: the Cartesian coordinate system
- - The above are the basis sets of the two- and three-dimensional Cartesian graphs, called the "standard basis set" (the Cartesian basis set consists of vectors that are mutually orthogonal and of unit length)
  - - The standard basis set is not the only basis set. T above is another basis set of R2
  - - In the example above, S and T both generate the same subspace. But T is preferred over S. (Because it is more concise and more intuitive)
- Definition of a basis
  - The combination of span and independence (if a vector set generates a particular subspace and is a linearly independent set, it is a basis of that subspace)

The unit balls of the three norms, and then the same least-squares contours meeting an L2 ball and an L1 ball. The L2 ball is smooth, so first contact happens at a generic point with both coordinates non-zero. The L1 ball has corners on the axes, and contact at a corner sets a coordinate to exactly zero. That geometric difference is the entire reason lasso selects features and ridge does not.
Matrix norm (||A||)
- The matrix norm is an extension of the vector norm (the Euclidean geometric length, the square root of the sum of the squares of the vector elements)
- A matrix has several different norms (the element-wise family and the induced family)
- Element-wise norm: a norm computed on the basis of the individual elements of the matrix → interpreted as reflecting the magnitude of the matrix elements
  - Frobenius norm (Euclidean norm, L2 norm)
    - Computed as the square root of the sum of the squares of all matrix elements
    - In the expression below, i and j denote the row and the column respectively, and F denotes the Frobenius norm
    - Applied in machine learning and statistical analysis among others → the most important application is regularization (whose goal is to improve model fit and increase the generalization performance of the model)
      - L2 regularization (ridge regression): prevents the model parameters from becoming too large
      - L1 regularization (lasso regression): prevents sparse results from appearing
    - Also applied when computing "matrix distance" - the distance between identical matrices is 0, and the larger the difference between the numbers inside the matrices, the larger the norm
      - Used as an optimization criterion in machine learning: reducing the data size while minimizing the Frobenius distance between the reduced matrix and the original matrix
    - The Frobenius norm can be computed as the square root of the trace of the product of a matrix with its own transpose
      - Why it holds: because each diagonal element of AᵀA is the dot product of a row with itself
- Induced norm: a measure of how much the norm of a vector is rescaled by the transformation
Matrix spaces
- Linear weighted combinations between the different features of a matrix (matrix spaces are also an extension of vector subspaces)
- Column space
  - The infinite set of vectors generated as the result of linearly combining a matrix made of a set of column vectors with infinitely many scalars, written as C(A)
  - It is important that having N columns in a matrix does not automatically make the column space N-dimensional
  - The number of dimensions of the column space equals the number of columns only when the columns form a linearly independent set
    - A set is linearly independent when no vector in the set can be expressed as a linear combination of the other vectors of that set.
- Row space
  - Exactly the same concept as the column space, dealing with all possible weighted combinations of rows instead of columns
  - The row space is written as R(A), R(A) = C(Aᵀ)
- Null space ~ plays a central role in finding eigenvectors and singular vectors
  - The set of vectors that linearly combine the columns to produce the zero vector
  - Ay = 0, N(A)
  - A vector y satisfying the equation above lies in the null space of A
  - The dot product between a null-space vector and each row is 0 (the row space and the null space are orthogonal)
  - Notation for an empty null space of a matrix: N(A) = { }
- Rank-nullity theorem
  - If the columns of a matrix form a linearly independent set, the null space is empty.
    - Full-rank and full-column-rank matrices have an empty null space, whereas the null space of a reduced-rank matrix is not empty

The four subspaces of a rank-2 matrix in R^3, computed from its SVD. The column space is a plane and the left null space is the line perpendicular to it; the row space is a plane and the null space is the line perpendicular to it. The caption prints ||A . null|| and the row-null inner product, both at numerical zero -- the orthogonality is verified, not drawn.
Rank: the number of linearly independent column vectors in a matrix
- A unique number associated with a single matrix. It relates to the number of dimensions of the matrix subspaces and carries important meaning in matrix operations, such as determining the inverse or the number of solutions of an equation
- The rank is a non-negative integer
- Every matrix has one unique rank
- The rank of a matrix is written r(A) or rank(A) and is read "A is a rank-r matrix"
- The maximum rank a matrix can have is the smaller of the number of rows and the number of columns, i.e. a matrix for which r = min{M, N}
- A matrix having the maximum possible rank is called full rank
- A matrix with rank r < min{M, N} is variously called "reduced rank", "rank deficient" or "singular"
- Scalar multiplication does not affect the rank of a matrix
- Equivalent interpretations and definitions of matrix rank
  - The maximum number of columns (or rows) that form a linearly independent set
  - The number of dimensions of the column space (identical to the number of dimensions of the row space)
  - The number of dimensions containing information in the matrix. It is not equal to the total number of columns or rows of the matrix, since they may be linearly dependent
  - The number of nonzero singular values in the matrix
- Practice
```
  A = [[1], [2], [3]], r(A) = 1
  B = [[1, 3], [2, 6], [4, 12]], r(B) = 1
  C = [[1, 3.1], [2, 6], [4, 12]], r(C) = 2
  D = [[1, 3, 2], [6, 6, 1], [4, 2, 0]], r(D) = 3(full-rank)
  E = [[1, 1, 1], [1, 1, 1], [1, 1, 1]], r(E) = 1
  F = [[0, 0, 0], [0, 0, 0], [0, 0, 0]], r(F) = 0
```
Rank of special matrices
- Vectors: the rank of every vector is 1 (because a vector has only a single column or row of information. The only exception is the zero vector)
- Zero matrix: the rank of a zero matrix (including the zero vector) of any size is 0
- Unit matrix: the rank of a unit matrix equals its number of rows (= its number of columns). That is, r(IN) = N
- Diagonal matrix: the rank of a diagonal matrix equals the number of nonzero diagonal elements ~ this property is useful when solving equations or interpreting a singular value decomposition
- Triangular matrix: full rank only when every diagonal element is nonzero; a triangular matrix with one or more zeros on the diagonal is reduced rank
- Random matrix: the rank of a random matrix is unknown, but there are ways of building the matrix so that the maximum possible rank is guaranteed (drawing floating-point numbers at random from a Gaussian or uniform distribution, for example)
- Rank-1 matrix: taking the outer product between two nonzero vectors produces a rank-1 matrix
Rank of summed and multiplied matrices
- Knowing the ranks of the individual matrices does not give the exact rank of the summed or multiplied matrix (the zero matrix being the exception)
- What the individual ranks do give is the maximum possible rank the resulting matrix can have
- rank(A+B) ≤ rank(A) + rank(B)
  - The rank of a summed matrix can be larger than the ranks of the individual matrices
- rank(AB) ≤ min{rank(A), rank(B)}
  - The rank of a product matrix cannot exceed the largest rank among the individual matrices (which is why an outer product always produces a rank-1 matrix)
Rank of a shifted matrix
- Shifting a matrix usually makes it full rank (the main aim of shifting a square matrix is to raise the rank from r < M to r = M)
Applications of rank
- Algorithm for checking whether a vector lies in the column space of a matrix
  1. Augment the matrix with the vector (~A: the augmented matrix)
    - Augmenting a matrix means adding a column on the right of the matrix
  2. Compute the ranks of the two matrices
  3. Compare the two ranks
    - rank(A) = rank(~A): the vector lies in the column space of matrix A
    - rank(A) < rank(~A): the vector does not lie in the column space of matrix A
- Linear independence of a vector set
  - Algorithm for checking whether a vector set is linearly independent
    - Put the vectors into a matrix, compute the rank of the matrix, and compare it with the maximum possible rank of that matrix (min{M, N})
    - r = N: the vector set is linearly independent
    - r < M: the vector set is linearly dependent
Determinant
- The determinant is a number associated with a square matrix, written det(A) or |A|
- Important properties
  1. The determinant is defined only for square matrices
  - It can be obtained relatively simply for a 2x2 or 3x3 matrix, but the computation grows increasingly complicated as the size increases
  - When a determinant has to be computed, use np.linalg.det() or scipy.linalg.det()
  1. The determinant is 0 for every singular (reduced-rank) matrix
  - If r < M then Δ = 0
Characteristic polynomial of a matrix
- Combining a matrix shift with the determinant
- det(A - λI)Δ
- The solutions of the characteristic polynomial for which Δ = 0 are the eigenvalues of the matrix

An eigenvector is a direction the matrix does not rotate, only rescales. The left panel sends the unit circle through A and marks the two eigen-directions: input and output lie on the same line, and the ratio is the eigenvalue. The right panel takes a nearby non-eigen direction and measures how far it is rotated, which is what makes the eigen-directions special rather than typical. The reconstruction error of V.Lambda.V^-1 against A is printed.

Every matrix, including non-square and singular ones, factors as a rotation, a scaling along axes, and another rotation. The four panels apply V', Sigma and U in turn to the unit circle, and the singular values turn out to be the semi-axes of the resulting ellipse. The reconstruction error is printed to confirm the factorization is exact.

Summarization

A vector is numbers arranged in a column or a row, and the order matters. The number of elements of a vector is called its dimension. A vector can be represented as a single line in a geometric space having as many axes as its dimension.
Vector arithmetic such as addition, subtraction and the Hadamard product is computed element-wise.
The dot product is a single number encoding the relationship between two vectors of the same dimension, obtained by multiplying element-wise and summing (the dot product is very important. It is related to similarity).
If two vectors are orthogonal their dot product is 0, which geometrically means the vectors meet at a right angle (used in decomposition).
Orthogonal vector decomposition splits one vector into a vector orthogonal to the reference vector and a vector parallel to it (the formula can be derived geometrically, but what has to be remembered is the concept it embodies, a "mapping onto magnitude").
A vector set is a collection of vectors, and a vector set may contain a finite or infinite number of vectors.
A linear combination is multiplying the vectors of a set by scalars and summing them, and is the single most central concept in linear algebra.
If one vector in a set can be described as a linear combination of the other vectors of the set, that vector set is linearly dependent. If no such linear combination exists, the vector set is linearly independent.
A subspace is the infinite set made of all possible linear combinations of a vector set.
A basis is a concept much like a ruler for measuring a space. If a vector set (1) generates some subspace and (2) is linearly independent, it is a basis for that subspace. A major goal of data science is to find the best basis set for describing a data set or solving a problem.
A matrix is a table of numbers made of rows and columns
Various special matrices exist (random, square, nonsquare, diagonal, triangular (upper and lower), unit, zero and symmetric matrices)
Matrix arithmetic such as addition, scalar multiplication and the Hadamard product operates element-wise
Shifting a matrix is adding a constant to the diagonal elements (off-diagonal elements are not changed); shifting is mainly applied in areas such as finding eigenvalues or regularizing statistical models
Matrix multiplication is the dot product between the rows of the left matrix and the columns of the right matrix. Validity rule for matrix multiplication: (M x N)(N x K) = (M x K)
LIVE EVIL: the transpose of a product of several matrices equals transposing each matrix and multiplying them in reverse order
A symmetric matrix has the form reflected in the diagonal as a mirror, each row equals the corresponding column, and it is defined by A = Aᵀ
Multiplying any matrix by its own transpose (Aᵀ) produces a symmetric matrix; the resulting matrix AᵀA is central to statistical models and singular value decomposition
There are many kinds of matrix norm, broadly classified as element-wise and induced
- The former reflects the magnitude of the elements of the matrix, while the latter reflects the geometric transformation effect of the matrix on a vector
The most commonly used element-wise norm is called the Frobenius norm (that is, the Euclidean norm or l2 norm) and is computed as the square root of the sum of the squares of the elements
The trace of a matrix is the sum of its diagonal elements
There are four matrix spaces (column, row, null and left-null), defined as sets of linear weighted combinations of the different features of the matrix
The column space of a matrix consists of all linear weighted combinations of the columns in the matrix and is written C(A)
An important part of linear algebra is whether a given vector b lies in the column space of a matrix. If it does, there exists a vector x satisfying Ax = b
The row space of a matrix is the set of linear weighted combinations of the rows of the matrix, written R(A) or C(Aᵀ)
The null space of a matrix is the set of vectors that linearly combine the columns to produce the zero vector. That is, the vectors y satisfying the equation Ay = 0 (excluding the trivial solution y=0). The null space is important for finding eigenvectors, among other applications
The rank is a number associated with a matrix and is a non-negative integer. The rank is the largest number of columns (or rows) that can form a linearly independent set. A matrix with a rank smaller than the maximum possible rank is called reduced rank or singular
Shifting a square matrix by adding a constant to its diagonal usually makes it full rank
Rank can also be applied when deciding whether a vector lies in the column space of a matrix. Compare the rank of the matrix with the rank of the matrix augmented by the vector
The determinant is a number associated with a square matrix (a nonsquare matrix has no determinant).
- Most importantly, it is 0 for every reduced-rank matrix and nonzero for every full-rank matrix
The characteristic polynomial converts the determinant of a square matrix shifted by λ into an equation set to a particular value.

Theorem

The results the notes above rely on, each with what it is actually used for. The vector-space axioms are at the end, since they are the least consequential true statements in the subject.

T1. Cauchy-Schwarz inequality

|x'y| <= ||x|| ||y||, with equality exactly when x and y are parallel.

Why it matters: it is what makes cos(theta) = x'y / (||x|| ||y||) lie in [-1, 1], and therefore what makes the correlation coefficient and cosine similarity bounded quantities rather than arbitrary numbers.

T2. Triangle inequality

||x + y|| <= ||x|| + ||y||.

Follows from T1. It is the property that makes a norm a distance, and hence what lets "nearest neighbour" mean anything.

T3. Pythagorean theorem for orthogonal vectors

If x'y = 0 then ||x + y||^2 = ||x||^2 + ||y||^2.

This is why an orthogonal decomposition splits energy additively, and why the residual sum of squares and the explained sum of squares add to the total in regression.

T4. Orthogonal decomposition

For any vector b and any non-zero a, b decomposes uniquely as b = beta.a + r with r orthogonal to a, and beta = a'b / a'a.

Uniqueness is the part that matters: the projection is not one choice among many. It is the basis of least squares, Gram-Schmidt and QR.

T5. Rank-nullity theorem

For A of size m x n: rank(A) + dim N(A) = n.

Every dimension of the input is either preserved or destroyed, and the two counts must sum to n. This is what connects "how many solutions does Ax = b have" to "what is the rank of A".

T6. Fundamental theorem of linear algebra (the four subspaces)

For A of size m x n with rank r:

dim C(A) = r, dim C(A') = r -- the row rank and the column rank are equal, which is not obvious and is the theorem's real content
dim N(A) = n - r, dim N(A') = m - r
N(A) is the orthogonal complement of C(A') in R^n, and N(A') is the orthogonal complement of C(A) in R^m
The subspaces figure above verifies both orthogonality statements numerically on a rank-2 example.

T7. Invertible matrix theorem

For a square A of size n x n, the following are equivalent -- each one implies all the others:

A is invertible
det(A) != 0
rank(A) = n
N(A) = {0}, i.e. Ax = 0 has only the trivial solution
The columns of A are linearly independent
The columns of A span R^n, so Ax = b has a solution for every b
Ax = b has a unique solution for every b
0 is not an eigenvalue of A
All n singular values of A are non-zero

This is the most useful theorem in the subject in practice: it lets a question asked in one language be answered in whichever language is easiest.

T8. Spectral theorem

Every real symmetric matrix A can be written A = Q.Lambda.Q' with Q orthogonal and Lambda real diagonal.

Real eigenvalues, orthogonal eigenvectors, always diagonalizable -- none of which holds for general matrices.
Why it is everywhere: covariance matrices, Gram matrices A'A, Hessians and graph Laplacians are all symmetric. PCA is this theorem applied to a covariance matrix.

T9. Positive definiteness

A symmetric A is positive definite iff all its eigenvalues are positive, iff x'Ax > 0 for all non-zero x, iff it has a Cholesky factorization A = LL'.

A'A is always positive semi-definite, and it is positive definite exactly when A has full column rank. That is the condition for the normal equations to have a unique solution.

T10. Singular value decomposition

Every matrix A of size m x n, square or not, factors as A = U.Sigma.V' with U and V orthogonal and Sigma diagonal with non-negative entries.

Unconditional existence is the point: eigendecomposition needs squareness and diagonalizability, SVD needs nothing.
The singular values are the square roots of the eigenvalues of A'A, and rank(A) is the number of non-zero singular values.

T11. Eckart-Young theorem

The best rank-k approximation of A in the Frobenius (and spectral) norm is obtained by keeping the k largest singular values and zeroing the rest.

"Best" here means a global optimum of a non-convex problem, obtained in closed form -- an unusual and valuable situation.
This is why PCA, low-rank compression and latent-factor recommenders are all the same computation.

T12. Normal equations

The least squares solution of Ax ~ b satisfies A'Ax = A'b, and the residual b - Ax is orthogonal to C(A).

Orthogonality is not an extra condition, it is equivalent to minimizing the residual: the closest point in a subspace is the foot of the perpendicular. T4, in the dimension of the problem.

T13. Gram-Schmidt and QR

Any matrix with linearly independent columns factors as A = QR with Q having orthonormal columns and R upper triangular.

The figure above runs the process one column at a time and prints ||Q'Q - I|| and ||A - QR||.
Numerically, the classical algorithm loses orthogonality on ill-conditioned input; modified Gram-Schmidt or Householder reflections are what production code uses.

T14. Trace and determinant identities

tr(A) = sum of eigenvalues, det(A) = product of eigenvalues
tr(AB) = tr(BA), even when AB and BA have different sizes
det(AB) = det(A)det(B)
The first pair is why the trace and determinant can be computed without ever forming the eigenvalues, and the cyclic property of the trace is the workhorse identity in matrix calculus.

Vector space axioms

1.1.1. When x, y, z are vectors in R^n and h and k are scalars,

(1) x + y = y + x
(2) (x + y) + z = x + (y + z)
(3) x + 0 = x = 0 + x
(4) x + (-x) = 0 = (-x) + x
(5) k(x + y) = kx + ky
(6) (h + k)x = hx + kx
(7) (hk)x = h(kx)
(8) 1x = x

1.1.2 When x is a vector in R^n and k is a scalar,

(1) 0x = 0
(2) k0 = 0
(3) (-1)x = -x

etc) Reducing a rectangular matrix to reduced row echelon form yields exactly one reduced row echelon matrix; that is, no other reduced row echelon form exists. (Lay p.13)

Vector applications

Correlation
- Correlation is the most fundamental and important analysis method in statistics and machine learning: the dot product between two variables, normalized by the magnitude of the variables
  - Correlation coefficient: a number quantifying the linear relationship between two variables (ranging from -1 (negative correlation) to +1 (positive correlation))
  - Normalization is needed for the correlation coefficient to lie in the expected range of -1 to +1
    1. Mean-centring each variable: subtracting the mean value from each data value
    2. Pearson correlation coefficient (dividing the dot product by the product of the vector norms)
    - The full formula for the Pearson correlation coefficient
    - The Pearson correlation coefficient expressed in linear-algebra terms (using dot product notation, where x~ is x mean-centred)
      - It must be remembered that the formula below is a simplification that assumes the variables have been mean-centred
Cosine similarity
- Another way of assessing the similarity between two variables, similar to correlation
- Obtained by taking the cosine term from the geometric formula of the dot product (α = cos(θA, B) ||A|| ||B||, (-1 <= cos(θA, B) <= +1)) (α is the dot product of A and B)
Difference between correlation and cosine similarity
- From the perspective of Pearson correlation, if one variable changes with the other, the numerical difference between the variables does not affect the result
- From the perspective of cosine similarity, if one variable changes with the other, the numerical difference between the variables does affect the result
Time series filtering and feature detection
- Filtering is essentially a feature detection technique
  - A template (kernel) searches for features matching part of a time series signal (the kernel is constructed to be optimized for a particular criterion, e.g., smooth fluctuation, a sharp edge, a specific waveform shape)
  - The filtered result becomes another time series, through which it can be seen how well the characteristics of the signal match the characteristics of the kernel
- The filtering mechanism is computing the dot product between the kernel and the time series signal
  - The dot product is computed between the kernel and a short data segment of the same length as the kernel; this process produces one point in the filtered signal segment, and the kernel is then shifted one segment to the right to compute the dot product with another signal segment, and so on
    - This process is called convolution
k-means clustering
- k-means clustering: an unsupervised technique that classifies multivariate data into a relatively small number (k) of groups or categories so as to minimize the distance to the group centres
- Algorithm
  1. Initialize k arbitrary cluster centroids in the data space (here the centroids are the classes or categories; in the next step each data observation is assigned to a class)
  2. Compute the Euclidean distance between each data observation and each centroid
    - Linear algebra concepts are used when computing the Euclidean distance between a data observation and a centroid
  3. Assign each data observation to the group of the nearest centroid (this can be done efficiently using vectors and broadcasting instead of a double for loop)
  4. Update each centroid to the mean of all data observations assigned to that centroid
  5. Repeat steps 2-4 until the convergence criterion is met, or up to N times

Matrix applications

Covariance matrix of multivariate data
Geometric transformation through matrix-vector multiplication
Image feature detection

PCA is T8 applied to a covariance matrix, and the figure does exactly that: it forms the covariance of the centred data, takes its eigendecomposition, and draws the eigenvectors scaled by the square root of their eigenvalues. Rotating the data onto those axes leaves an off-diagonal covariance at numerical zero -- decorrelation, verified. The explained-variance split is printed in the title.

The normal equations of T12, fitted and then checked. The left panel draws the residuals being minimized; the right plots residual against fitted value and prints A'r, which is at numerical zero. That is the orthogonality condition holding, and it is what makes the fit the closest point in the column space rather than merely a good one.

Gram-Schmidt run one column at a time: each new vector has the part already explained by the previous ones subtracted off, then is normalized. The fourth panel shows Q'Q coming out as the identity to numerical precision, and the caption prints the QR reconstruction error.

Eckart-Young (T11) in practice. The singular values of a structured matrix decay quickly, so a rank-3 approximation already captures most of it and rank-10 is visually indistinguishable from the original. The relative error is printed on each panel. This one figure is simultaneously PCA, image compression and the latent-factor model behind collaborative filtering -- they differ in what the matrix contains, not in the computation.

Figures

Regenerate with python make_figures.py (numpy and matplotlib only). Every panel is computed from the matrix it describes, and every decomposition prints its own reconstruction error, so a figure cannot quietly disagree with the text.

References

https://m.blog.naver.com/kiseop91

Name		Name	Last commit message	Last commit date
Practice Folder		Practice Folder
Study Resources		Study Resources
figures		figures
.gitignore		.gitignore
README.md		README.md
make_figures.py		make_figures.py

Navigation Menu

Repository files navigation

Linear_Algebra

Contents

Learning Notes

1. Elements in linear algebra

2. Linear System

3. Linear combination, vector equation, Four views of matrix multiplication

4. Linear independence, span, and subspace

Summarization

Theorem

T1. Cauchy-Schwarz inequality

T2. Triangle inequality

T3. Pythagorean theorem for orthogonal vectors

T4. Orthogonal decomposition

T5. Rank-nullity theorem

T6. Fundamental theorem of linear algebra (the four subspaces)

T7. Invertible matrix theorem

T8. Spectral theorem

T9. Positive definiteness

T10. Singular value decomposition

T11. Eckart-Young theorem

T12. Normal equations

T13. Gram-Schmidt and QR

T14. Trace and determinant identities

Vector space axioms

Vector applications

Matrix applications

Figures

References

About

Releases

Packages

Contributors

Languages

Latest commit

History

Folders and files

Repository files navigation

Linear_Algebra

Contents

Learning Notes

1. Elements in linear algebra

2. Linear System

3. Linear combination, vector equation, Four views of matrix multiplication

4. Linear independence, span, and subspace

Summarization

Theorem

T1. Cauchy-Schwarz inequality

T2. Triangle inequality

T3. Pythagorean theorem for orthogonal vectors

T4. Orthogonal decomposition

T5. Rank-nullity theorem

T6. Fundamental theorem of linear algebra (the four subspaces)

T7. Invertible matrix theorem

T8. Spectral theorem

T9. Positive definiteness

T10. Singular value decomposition

T11. Eckart-Young theorem

T12. Normal equations

T13. Gram-Schmidt and QR

T14. Trace and determinant identities

Vector space axioms

Vector applications

Matrix applications

Figures

References

About

Resources

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages