Linear Algebra Part 1
May 3, 2016
This is the summary of the topics covered by Gilbert Strang in his lectures
Table of Contents:
Lectures 15
Covers the basic matrix concepts
 Matrix Row picture and Column picture
 Can we solve for \(Ax=b\) for all \(b\) ?. No, only for \(b\)’s in the column space of \(A\).
Four ways of matrix multiplication
 Dot product
 Column picture
 Row picture
 Column times Row
Gaussian Elimination
 Operates on the rows of matrix \(A\), finally puts the matrix in Row Reduced Echelon(REF) form
 Gaussian elimination leads to \(A = LU\) form, and \(A = LDU\) form
 Helps to put the elements of \(A\), in the Row Reduced Echelon Form (RREF) form

Can be used to solve for \(x\) in \(Ax = b\), by finding **_RREF([\(A\) 
\(b\)])** which results in **[\(I\) 
\(x\)]_** 

Can be used to find the inverse of the matrix \(A\) by finding **_RREF[\(A\) 
\(I\)]** which results in **[\(I\) 
\(A^{1}\)]_** 
Permutation matrix
 Number of permutation matrix \(A_{N*N} = N!\)
 \(P^T = P\) (where \(P^T\) is transpose(\(P\)))
 \(P P^T = I\) (Can you prove? Hint: use definition of matrix multiplication) * If the number of equations are less than number of variables, why we cannot solve the equation? * This is because rank of the matrix will be less than the number of variables we need to solve, so it will have infinite number of solutions * Use RREF(\(A\)) in matlab/octave and check
 \(A A^T\) is symmetric, prove!
Lectures 610
Vector Space

All linear combination of vectors are in the space, called Vector Space

Say \(P\) and \(L\) are two subspaces
 Is \(P\cup L\) a subspace? No, because some combination of vector \(A \in P\) and vector \(B \in L\) might not be in the subspace \(P\cup L\).
Column Space and Null Space

Column Space C(\(A\)) is all possible linear combinations of column vectors in a matrix \(A\)

Null Space N(\(A\)) is all the \(x\)’s for which \(Ax = 0\)

Elimination process will change Column Space of \(A\), but not the Null space of \(A\)
 This is because in the elimination process we change \(A\), but not \(x\).
Basic and Free Variables

The real difference between basic variables and free variables is that the free variables can be anything, and the basic variables are determined by solving the equations

Basic variables are also called as Pivot variables. The columns with these variables are called Pivot columns

Number of Pivot columns = Rank r of the matrix = Number of independent columns in the matrix

Number of Free columns = n  r ( n = number of columns in matrix \(A))
Solution for Ax = b
Rank tells you everything about the number of solutions
 Full column rank matrix: Unique solution exists, if \(b\) lies in column space of \(A\)
 Full row rank matrix: Infinite number of solutions
 Full row rank/ full column rank: Unique solution always exists for all \(b\)
 No full column rank/ No full row rank: Infinitely many solution exists if \(b\) lies in column space of \(A\)
Basis
 Basis of a vector space is sequence of vectors \(v_1, v_2, v_3, …, v_N\) with the following properties
 They are independent
 They span a space
Four Subspaces
For a matrix \(A_{m*n}\)
 Column space C(\(A\)): combination of columns of \(A\), lies in \(R^n\)
 Null space N(\(A^T\)) : left null space of \(A\), lies in \(R^n\)
 Row space R(\(A\)): combination of columns of \(A^T\), lies in \(R^m\)
 Null space N(\(A\)): right null space of \(A\), lies in \(R^m\)
 Row operation on a matrix \(A\) changes the column space of \(A\), but preserves the row space of \(A\)
## Lectures 1115
Vector Space of Matrices
 Consider vector space of matrices \(A_{N*N}\)
 Dimension of vector space of symmetric matrices = \((N^2 + N)/2\)
 Dimension of vector space of skew symmetric matrices = \((N^2  N)/2\)
 Dimension of vector space of upper triangular matrices = \((N^2 + N)/2\)
 (Symmetric matrix \(\cap\) Upper triangular matrices) = Diagonal
matrices. Dimension of vector space = \((N^2  N)/2\)
 (Symmetric matrix \(\cup\) Upper triangular matrices) = All \(N*N\) matrices. Dimension of vector space = \(N^2\)
Rank1 Matrices
 They are special case
 They are building blocks for every other matrices
 Matrices with Rank1 are separable matrices ( this is the
application in image processing for separating the filters)
Orthogonality
 Prove that two vectors \(X\) and \(Y\) are orthogonal to each other if
\(X^T Y = 0 = Y^T X\)
 Row space is perpendicular to Right null space , i.e., every vector
in row space is perpendicular to every other vector in right
null space
 Column space is perpendicular to left null space, i.e., every
vector in column space is perpendicular to every other vector
in left null space
Projection Matrix
 Projection of vector \(b\) onto vector \(a\) is defined as \(p = Pb\), where \(P = (a a^T)/(a^T a) \)
 Column space of projection matrix \(P\) is column space of \(a\). i.e., line through \(a\)
 Properties of Projection matrices
 Projection matrix in general
 We have \(A^T A \hat{x} = A^T B\)
 \(P = A \hat{x}\), where \(\hat{x} = (A^T A)^{1} A^T B\)
and \(P = A (A^T A)^{1} A^T \)
Least square problem
 Why projection ?
 When we have only few unknowns, but many equations to solve
\(Ax = b\), \(b\) might not be the column space of
\(A\)
 To solve for \(x\), we project \(b\) onto columns
space of \(A\), so that the new vector \(\bar{b}\) is closest
to \(b\)
 Eg. Measuring pulse of the heart, but repeatedly we take
measurements so that on an average we can estimate the pulse.
For more detailed treatment of least squares,
link
 The pictorial representation of solving least squares is shown below
 Least squares: \(\bar{x}\) minimizes \(b  Ax\) by solving \(A^T A \bar{x} = A^T b\)
 \(A^T A\) is invertible, if \(A\) has independent columns, prove
it