Introduction to Linear Algebra
Systems of Linear Equations
- Introduction
- Linear Systems
- Vectors
- Linear combinations
- Matrices
- Planes in ℝ³
- Reduced Row-Echelon Form
- Equation A x = b
- Sensitivity of solutions
- Linear independence
- Plane transformations
- Space transformations
- Rotations
- Linear transformations
- Affine maps
- Exercises
- Answers
Matrix Algebra
- Introduction
- Manipulation of matrices
- Partitioned matrices
- Block matrices Matrix operators
- Determinants
- Cofactors
- Cramer's rule
- Equivalent matrices
- Elimination: A = LU
- PLU factorization
- Reflection
- Givens rotation
- Special matrices
- Exercises
- Answers
Vector Spaces
- Introduction
- Motivation
- Vector Spaces
- Bases
- Dimension
- Coordinate systems
- Change of basis
- Linear transformations
- Matrix transformations
- Compositions
- Isomorphisms
- Dual transformations
- Direct sums
- Quotient spaces
- Vector products
- Cross products
- Rank
- Solving A x = b
- Exercises
- Answers
Eigenvalues, Eigenvectors
- Introduction
- Characteristic polynomials
- Companion matrix
- Algebraic and geometric multiplicities
- Minimal polynomials
- Eigenspaces
- Where are eigenvalues?
- Eigenvalues of A B and B A
- Generalized Eigenvectors
- Similarity
- Diagonalizability
- Self-adjoint operators
Euclidean Spaces
- Introduction
- Dot product
- Bilinear transformations
- Inner product
- Norm and distance
- Matrix norms
- Dual norms
- Dual transformations
- Orthogonality
- Gram--Schmidt process
- Orthogonal sets
- Self-adjoint matrices
- Unitary matrices
- Projection operators
- QR-decomposition
- Least Square Approximation
- Quadratic forms
- Exercises
- Answers
Matrix Decompositions
- Introduction
- Symmetric matrices
- LU-decomposition
- Sylvester Formula
- Cholesky decomposition
- Schur decomposition
- Positive Matrices
- Roots
- Polar Factorization
- Spectral Decomposition
- Singular values
- SVD
- Pseudoinverse
- Exercises
- Answers
Applications
- GPS problem
- Poisson equation
- Graph theory
- Error correcting codes
- Electric circuits
- Markov chains
- Cryptography
- Wave-length transfer matrix
- Computer graphics
- Linear Programming
- Hill's determinant
- Fibonacci matrices
- Discrete dynamic systems
- Discrete Fourier transform
- Fast Fourier transform
- Curve fitting
Functions of Matrices
- Introduction
- Diagonalization
- Sylvester formula
- The Resolvent method
- Polynomial interpolation
- Positive matrices
- Roots
- Pseudoinverse
- Exercises
- Answers
Miscellany
- Circles along curves
- TNB frames
- Tensors
- Tensors in ℝ³
- Tensors & Mechanics
- Differential forms
- Calculus
- Vector Representations
- Matrix Representations
- Change of basis
- Orthonormal Diagonalization
- Generalized inverse
Preliminaries
- Complex Number Operations
- Sets
- Polynomials
- Polynomials and Matrices
- Computer solves systems of Linear Equations
- Location of eigenvalues
- Power method
- Iterative method
Glossary
Reference
This Book is licensed under Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License
Inverse of Partitioned Matrices
Every m-by-n matrix A ∈ 𝔽m×n defines a linear transformation 𝔽n×1 ⇾ 𝔽m×1 by mapping every input x from domain 𝔽n×1 into output y = A x from codomain 𝔽m×1. Therefore, a matrix can be considered as a linear operator acting on finite dimensional column vector space. This transformation can be naturally extended to Cartesian product vector spaces, TA : 𝔽n ⇾ 𝔽m. The set of all outputs is called the range or image of the transformation.
If there exists a linear map R : Y ⇾ X such that (T ∘ R)(y) = T(R)(y) = y for all y in the domain Y, then R is called a right inverse of T.
Left inverse
Mathematica code below serves to display any matrix as a matrix rather than the default display which is as a list of lists
Theorem 1: Let X and Y be vector spaces over the same field 𝔽, and let T : X ⇾ Y be a linear transformation. The transformation T has left inverse if and only if it is 1-to-1, i.e., injective.
If T is not injective, then there exists v ≠ 0 such that T(v) = 0, so T maps two distinct elements v and 0 into one (zero vector). Then the left inverse to T does not exist because L cannot restore v: \[ L \left( T({\bf v}) \right) = L \left( T({\bf 0}) \right) = {\bf 0} \ne {\bf v} . \]
Another constructive proof. Suppose that T is injective. Let α = {xi : i ∈ I} be a basis for X. Then β = {T(xi) : i ∈ I} is a linearly independent set that generates subspace U ⊆ Y. There exists a basis γ of Y that contains β. We construct a left inverse map L for T by the rule \[ L({\bf u}) = \begin{cases} {\bf v} , & \quad \mbox{if} \quad {\bf u} \in \mbox{span}\{ \beta \}, \quad \mbox{with} \quad {\bf u} = T({\bf v}) , \\ {\bf 0} , & \quad \mbox{if} \quad {\bf u} \not\in \mbox{span}\{\beta \} . \end{cases} \] Then for \( \displaystyle {\bf x} = \sum_i c_i {\bf x}_i \in X , \quad \) we have \[ L \left( T({\bf x}) \right) = L\,T \left( \sum_i c_i {\bf x}_i \right) = \sum_i c_i L\,T \left( {\bf x}_i \right) = \sum_i c_i {\bf x}_i = {\bf x} . \] Hence, L is a left inverse of T.
To find all left inverse matrices, we need to solve the equation X A = I, i.e., \[ \begin{bmatrix} x_1 & x_2 & x_3 \\ x_4 & x_5 & x_6 \end{bmatrix} \cdot \begin{bmatrix} 1&2 \\ 3&4 \\ 5&6 \end{bmatrix} = \begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} \]
augMat = ArrayFlatten[{{Transpose[A], iMat}}]
RowReduce[augMat2] M = {{1, 3, 5, 1}, {2, 4, 6, 0}};
(RowReduce[M]) // MatrixForm
Similarly, we use Mathematica to find the general solution of another set of variables (x₄, x₅, x₆):
({Subscript[x, 4], Subscript[x, 5]} /. soln2)[[1]] == Flatten[soln2C]
P.A
c = {{t, -2*t, t}, {s, -2*s, s}} ;
c.A
The n × n matrix ATA is symmetric and non-singular for every full column rank matrix A. Hence, (ATA)−1 ATA = In, the identity matrix. In this case, matrix (ATA)−1 AT is left inverse, which we denote by \( \displaystyle {\bf A}_{left}^{-1} . \) Note that this left inverse is not unique and there are could be many others.
Note that the left inverse is an n × m matrix, with m ≤ n. It can be also right inverse only when m = n. For a given left inverse \( \displaystyle {\bf A}_{left}^{-1} , \) adding a matrix C such that C A = 0 induces another left inverse.
Right inverse
Theorem 2: Let X and Y be vector spaces over the same field 𝔽, and let T : X ⇾ Y be a linear transformation. The transformation T has right inverse if and only if it is onto, i.e., surjective.
Now suppose that T is surjective. Let α = {xi : i ∈ I} be a basis of X. Then T(α) generates Y. Then there exits a subset β ⊆ T(α) that is a basis in Y. Now for every vector yi in β, yi = T(xi) for some vector xi ∈ X. The vector xi may not be unique, but that does not matter. Let R : Y ⇾ X be the linear transformation defined by R(yi) = xi. Then for each vector yi in the basis β of Y, T R(yi) = T(xi) = yi. This means that R is a right inverse of T.
On the other hand, suppose there is a linear transformation U : Y ⇾ X with T U = I. Then for any vector y ∈ Y, \[ {\bf y} = I({\bf y}) = T\,R({\bf y}) = T\left( R({\bf y}) \right) \] and so T is surjective.
B = {{1, 2, 3}, {4, 5, 6}};
B.Transpose[B]
BtB = Transpose[B] . B;
SymmetricMatrixQ[BtB]
Det[BtB]
0
To find all right inverse matrices, we need to solve the equation B X = I, i.e., \[ \begin{bmatrix} 1&2&3 \\ 4&5&6 \end{bmatrix} \, \begin{bmatrix} x_1 & x_4 \\ x_2 & x_5 \\ x_3 & x_6 \end{bmatrix} = \begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} . \] This leads to the system of six linear equations \[ \begin{split} x_1 + 2\, x_2 + 3\, x_3 &= 1 , \\ 4\, x_1 + 5\, x_2 + 6\, x_3 &= 0 , \\ x_4 + 2\, x_5 + 3\, x_6 &= 0 , \\ 4\, x_4 + 5\, x_5 + 6\, x_6 &= 1 . \end{split} \] We ask Mathematica to solve this system:
B . rr
Matrices with full row rank have right inverses \( \displaystyle {\bf A}_{right}^{-1} , \) with \( \displaystyle {\bf A}\,{\bf A}_{right}^{-1} = {\bf I} . \) We can choose as a right inverse the n × m matrix AT(A AT)−1.
Theorem 3: An n × m matrix X is left inverse of an m × n matrix A if and only if its adjoint X* is right inverse of A*.
A = {{1, 2}, {3, 4}, {5, 6}} ;
MatrixRank[A]
AtA = Transpose[A] . A
AAt = A.Transpose[A]
- Determine whether the following matrices are invertible \[ \mbox{(a)}\quad \begin{bmatrix} 1 & 2 & -3 \\ 0 & 5 & -1 \\ -1 & 2 & 2 \\ \end{bmatrix}, \qquad \mbox{(b)}\quad \begin{bmatrix} -3 & 3 & 2 \\ -1 & -2 & -1 \\ 0 & 2 & 1 \\ \end{bmatrix}, \qquad \mbox{(c)}\quad \begin{bmatrix} 2 & 1 & 3 \\ -2 & 1 & -2 \\ 3 & 2 & 5 \\ \end{bmatrix}, \qquad \mbox{(d)}\quad \begin{bmatrix} -2 & 1 & -1 \\ -3 & -3 & 3 \\ -1 & 3 & -3 \\ \end{bmatrix} . \]
- Use Gauss--Jordan elimination procedure to find the inverse of the matrix. \[ \mbox{(a)}\quad \begin{bmatrix} 1 & 2 & -3 \\ 0 & 5 & -1 \\ -1 & 2 & 2 \\ \end{bmatrix} , \qquad \mbox{(b)}\quad \begin{bmatrix} -3 & 3 & 2 \\ -1 & -2 & -1 \\ 0 & 2 & 1 \end{bmatrix} . \]
- Use the adjoint (adjugate) method to find the inverse of the matrix. \[ \mbox{(a)}\quad \begin{bmatrix} 3 & 3 & -1 \\ -2 & 0 & 3 \\ 2 & 1 & -2 \end{bmatrix} , \qquad \mbox{(b)}\quad \begin{bmatrix} -3 & -1 & -3 \\ 2 & 1 & 1 \\ 2 & 1 & 0 \end{bmatrix} . \]
- The n-by-n Hilbert matrix Hn = [hi,j] is given by \( \displaystyle h_{i,j} = \int_0^1 x^{i+j-2} {\text d} x = 1/(i + j − 1). \) Thus, \[ H_2 = \begin{bmatrix} 1 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{3} \end{bmatrix} , \qquad H_3 = \begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{3} & \frac{1}{4} \\ \frac{1}{3} & \frac{1}{4} & \frac{1}{5} \end{bmatrix} . \] Find inverse matrices above (for n = 2 and 3).
- Let A = [𝑎i,j] be the n-by-n matrix with 𝑎i,j = min{i, j} for 1 ≤ i, j ≠ n. Find A−1.
-
Prove the following identities for partitioned matrices.
- \( \displaystyle \begin{bmatrix} {\bf I} & {\bf B} \\ {\bf 0} & {\bf I} \end{bmatrix}^{-1} = \begin{bmatrix} {\bf I} & -{\bf B} \\ {\bf 0} & {\bf I} \end{bmatrix} \quad \) and \( \displaystyle \quad \begin{bmatrix} {\bf I} & {\bf 0} \\ {\bf C} & {\bf I} \end{bmatrix}^{-1} = \begin{bmatrix} {\bf I} & {\bf 0} \\ -{\bf C} & {\bf I} \end{bmatrix} . \)
- \( \displaystyle \begin{bmatrix} {\bf A} & {\bf 0} \\ {\bf 0} & \Lambda \end{bmatrix}^{-1} = \begin{bmatrix} {\bf A}^{-1} & {\bf 0} \\ {\bf 0} & \Lambda^{-1} \end{bmatrix} , \) where Λ is a diagonal matrix.
- Prove the identity for three invertible matrices: \[ \left( {\bf A}\,{\bf B}\,{\bf C} \right)^{-1} = {\bf C}^{-1} {\bf B}^{-1} {\bf A}^{-1} . \]
- Anton, Howard (2005), Elementary Linear Algebra (Applications Version) (9th ed.), Wiley International
- Beezer, R.A., A First Course in Linear Algebra, 2017.
- Dobrushkin, V.A., Applied Differential Equations. The Primary Course, second edition, CRC Press2022.
- Fadeev--LeVerrier algorithm, Wikipedia.
- Frame, J.S., A simple recursion formula for inverting a matrix, Bulletin of the American Mathematical Society, 1949, Vol. 55, p. 1045. doi:10.1090/S0002-9904-1949-09310-2
- Greenspan, D., Methods of matrix inversion, The American mathematical Monthly, 1955, Vol. 62, No. pp. 303--318.
- Karlsson, L., Computing explicit matrix inverses by recursion, Master's Thesis in Computing Science, 2006.
- Lightstone, A.H., Two methods of inverting matrices, Mathematics Magazine, 1968, Vol. 41, No. 1, pp. 1--7.