Ch.7: Theoretical linear algebra
Chapter 7 of the book "No Bullshit Guide to Linear Algebra" by Ivan Savov Eigenvalues and eigenvectors Special types of matrices Abstract vector spaces Abstract inner product spaces Gram–Schmidt orthogonalization Matrix decompositions Linear algebra with complex numbers
181 flashcards · Mathematics · by lakesare
Part of Textbooks › No Bullshit Guide to Linear Algebra (Ivan Savov) · 10 courses
[Eigenvalues and eigenvectors] What is an eigenvector e⃗λ\vec{e}_\lambdaeλ of a square matrix AAA , and its eigenvalue λ\lambdaλ ?
A nonzero vector with Ae⃗λ=λe⃗λA\vec{e}_\lambda = \lambda\vec{e}_\lambdaAeλ=λeλ : multiplying by AAA gives the same vector scaled by the number λ\lambdaλ . Ae⃗λ=λe⃗λA\vec{e}_\lambda = \lambda\vec{e}_\lambdaAeλ=λeλ is the eigenvalue equation.Example: [9−2−26]\begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix}[9−2−26] times (1,2)T(1, 2)^{\mathsf{T}}(1,2)T is (5,10)T=5 (1,2)T(5, 10)^{\mathsf{T}} = 5\,(1, 2)^{\mathsf{T}}(5,10)T=5(1,2)T , so (1,2)T(1, 2)^{\mathsf{T}}(1,2)T is an eigenvector with ei…
[Eigenvalues and eigenvectors] A basis of Rn\mathbb{R}^nRn made of eigenvectors of an n×nn \times nn×n matrix AAA is called the eigenbasis of AAA .
"Eigen" is German for "self": the eigenbasis is the matrix's own basis, the one in which the action of AAA is easiest to describe.
[Eigenvalues and eigenvectors] What is the eigendecomposition of an n×nn \times nn×n matrix AAA ?
A=QΛQ−1\boldsymbol{A = Q\Lambda Q^{-1}}A=QΛQ−1 , with the eigenvectors of AAA as the columns of QQQ and its eigenvalues on the diagonal of the diagonal matrix Λ\LambdaΛ . It is a change of basis that expresses AAA in its eigenbasis (the matrix's "natural basis"). Λ\LambdaΛ is the capital Greek letter lambda.Example: [9−2−26]=[122−1][50010][152525−15]\begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix} \begin{bmatrix} 5 & 0 \\ 0 & 10 \end{bmatrix} \begin…
[Eigenvalues and eigenvectors] AAA is an n×nn \times nn×n matrix. What is its characteristic polynomial p(λ)p(\lambda)p(λ) , and how is it related to the eigenvalues?
p(λ)=det(A−λ1 1)\boldsymbol{p(\lambda) = \det(A - \lambda\mathrm{1\!\!1})}p(λ)=det(A−λ11) , a polynomial of degree nnn in λ\lambdaλ whose roots are the eigenvalues of AAA . 1 1\mathrm{1\!\!1}11 is the identity matrix. Eigenvalues are found by solving p(λ)=0p(\lambda) = 0p(λ)=0 .Example: for [9−2−26]\begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix}[9−2−26] : p(λ)=(9−λ)(6−λ)−4=λ2−15λ+50p(\lambda) = (9 - \lambda)(6 - \lambda) - 4 = \lambda^2 - 15\lambda + 50p(λ)=(9−λ)(6−λ)−4=λ2−15λ+50 .
[Eigenvalues and eigenvectors] Why are the eigenvalues of AAA exactly the solutions of det(A−λ1 1)=0\det(A - \lambda\mathrm{1\!\!1}) = 0det(A−λ11)=0 ?
Ae⃗=λe⃗A\vec{e} = \lambda\vec{e}Ae=λe is the same as (A−λ1 1)e⃗=0⃗(A - \lambda\mathrm{1\!\!1})\vec{e} = \vec{0}(A−λ11)e=0 , which has a nonzero solution e⃗\vec{e}e exactly when A−λ1 1A - \lambda\mathrm{1\!\!1}A−λ11 is not invertible, i.e. has determinant 0. So finding eigenvalues is finding the λ\lambdaλ for which A−λ1 1A - \lambda\mathrm{1\!\!1}A−λ11 has a nonzero null space.
[Eigenvalues and eigenvectors] Find the eigenvalues of A=[9−2−26]A = \begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix}A=[9−2−26] .
λ1=5, λ2=10\boldsymbol{\lambda_1 = 5, \ \lambda_2 = 10}λ1=5, λ2=10 det(A−λ1 1)=(9−λ)(6−λ)−(−2)(−2)=λ2−15λ+50=(λ−5)(λ−10)\det(A - \lambda\mathrm{1\!\!1}) = (9 - \lambda)(6 - \lambda) - (-2)(-2) = \lambda^2 - 15\lambda + 50 = (\lambda - 5)(\lambda - 10)det(A−λ11)=(9−λ)(6−λ)−(−2)(−2)=λ2−15λ+50=(λ−5)(λ−10) .
[Eigenvalues and eigenvectors] How do you find the eigenvectors of AAA that belong to an eigenvalue λi\lambda_iλi ?
Compute the null space of (A−λi1 1)(A - \lambda_i\mathrm{1\!\!1})(A−λi11) : its nonzero vectors are the eigenvectors for λi\lambda_iλi . i.e. solve (A−λi1 1)e⃗λi=0⃗(A - \lambda_i\mathrm{1\!\!1})\vec{e}_{\lambda_i} = \vec{0}(A−λi11)eλi=0 , for instance with Gauss–Jordan elimination.
[Eigenvalues and eigenvectors] A=[9−2−26]A = \begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix}A=[9−2−26] has eigenvalues 5 and 10.Find an eigenvector for each eigenvalue.
λ=5\lambda = 5λ=5 : (1,2)T\boldsymbol{(1, 2)^{\mathsf{T}}}(1,2)T ; λ=10\ \lambda = 10 λ=10 : (2,−1)T\boldsymbol{(2, -1)^{\mathsf{T}}}(2,−1)T (or any nonzero multiples) A−51 1=[4−2−21]A - 5\mathrm{1\!\!1} = \begin{bmatrix} 4 & -2 \\ -2 & 1 \end{bmatrix}A−511=[4−2−21] needs 2x=y2x = y2x=y ; A−101 1=[−1−2−2−4]\ A - 10\mathrm{1\!\!1} = \begin{bmatrix} -1 & -2 \\ -2 & -4 \end{bmatrix} A−1011=[−1−2−2−4] needs x=−2yx = -2yx=−2y .
[Eigenvalues and eigenvectors] If e⃗λ\vec{e}_\lambdaeλ is an eigenvector of AAA with eigenvalue λ\lambdaλ , which other vectors are eigenvectors with eigenvalue λ\lambdaλ ?
Every multiple αe⃗λ\alpha\vec{e}_\lambdaαeλ with α≠0\alpha \neq 0α=0 : only the direction of an eigenvector matters, not its length. A(αe⃗λ)=αAe⃗λ=λ(αe⃗λ)A(\alpha\vec{e}_\lambda) = \alpha A\vec{e}_\lambda = \lambda(\alpha\vec{e}_\lambda)A(αeλ)=αAeλ=λ(αeλ) . So any such multiples can be the columns of QQQ in A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 .Example: (1,2)T(1, 2)^{\mathsf{T}}(1,2)T and (−3,−6)T(-3, -6)^{\mathsf{T}}(−3,−6)T are both eigenvectors of [9−2−26]\begin{bmatrix} 9 & -2 \\ -2 & 6 \…
[Eigenvalues and eigenvectors] What is the eigenspace EλiE_{\lambda_i}Eλi of an eigenvalue λi\lambda_iλi of A∈Rn×nA \in \mathbb{R}^{n \times n}A∈Rn×n ?
Eλi=N(A−λi1 1)={v⃗∈Rn∣(A−λi1 1)v⃗=0⃗}\boldsymbol{E_{\lambda_i} = \mathcal{N}(A - \lambda_i\mathrm{1\!\!1}) = \{\vec{v} \in \mathbb{R}^n \mid (A - \lambda_i\mathrm{1\!\!1})\vec{v} = \vec{0}\}}Eλi=N(A−λi11)={v∈Rn∣(A−λi11)v=0} N\mathcal{N}N is the null space. Its nonzero vectors are the eigenvectors for λi\lambda_iλi , and it always contains at least one.Example: for 1 1∈R2×2\mathrm{1\!\!1} \in \mathbb{R}^{2 \times 2}11∈R2×2 , E1=N(0)=R2E_1 = \mathcal{N}(\mathbb{0}) = \mathbb{R}^2E1…
[Eigenvalues and eigenvectors] What does eig(A)\operatorname{eig}(A)eig(A) denote, and how are repeated eigenvalues listed?
eig(A)=(λ1,λ2,…,λn)\boldsymbol{\operatorname{eig}(A) = (\lambda_1, \lambda_2, \dots, \lambda_n)}eig(A)=(λ1,λ2,…,λn) , the list of eigenvalues of AAA ; an eigenvalue that is a repeated root of p(λ)p(\lambda)p(λ) appears as many times as its multiplicity. Example: eig(1 12)=(1,1)\operatorname{eig}(\mathrm{1\!\!1}_2) = (1, 1)eig(112)=(1,1) , since the characteristic polynomial is (λ−1)2(\lambda - 1)^2(λ−1)2 .
[Eigenvalues and eigenvectors] What is a degenerate eigenvalue, and what is its algebraic multiplicity?
Degenerate: a repeated root of the characteristic polynomial p(λ)p(\lambda)p(λ) . Algebraic multiplicity: how many times it is a root. Example: 1 1∈R2×2\mathrm{1\!\!1} \in \mathbb{R}^{2 \times 2}11∈R2×2 has p(λ)=(λ−1)2p(\lambda) = (\lambda - 1)^2p(λ)=(λ−1)2 , so λ=1\lambda = 1λ=1 is degenerate with algebraic multiplicity 2.
[Eigenvalues and eigenvectors] What is the geometric multiplicity of an eigenvalue λi\lambda_iλi of AAA ?
The dimension of the null space of (A−λi1 1)(A - \lambda_i\mathrm{1\!\!1})(A−λi11) , i.e. the number of linearly independent eigenvectors for λi\lambda_iλi . For a degenerate eigenvalue it can be more than 1.Example: λ=1\lambda = 1λ=1 of 1 1∈R2×2\mathrm{1\!\!1} \in \mathbb{R}^{2 \times 2}11∈R2×2 has geometric multiplicity 2, since N(1 1−1 1)=R2\mathcal{N}(\mathrm{1\!\!1} - \mathrm{1\!\!1}) = \mathbb{R}^2N(11−11)=R2 .
[Eigenvalues and eigenvectors] When is an n×nn \times nn×n matrix AAA diagonalizable?
When it has nnn linearly independent eigenvectors (an eigenbasis of Rn\mathbb{R}^nRn ), so that A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 with Λ\LambdaΛ diagonal. nnn linearly independent vectors in Rn\mathbb{R}^nRn form a basis, so QQQ is invertible.
[Eigenvalues and eigenvectors] Why is an n×nn \times nn×n matrix with nnn distinct eigenvalues always diagonalizable?
Eigenvectors for different eigenvalues are linearly independent, so one eigenvector per eigenvalue gives nnn independent vectors, a basis of Rn\mathbb{R}^nRn . With degenerate eigenvalues, linearly independent eigenvectors are picked within each eigenspace; together they may or may not number nnn .
[Eigenvalues and eigenvectors] What are the steps to compute the eigendecomposition A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 of a diagonalizable matrix AAA ?
Eigenvalues Solve det(A−λ1 1)=0\det(A - \lambda\mathrm{1\!\!1}) = 0det(A−λ11)=0 for λ1,…,λn\lambda_1, \dots, \lambda_nλ1,…,λn . Eigenvectors For each λi\lambda_iλi , find a basis of the null space of (A−λi1 1)(A - \lambda_i\mathrm{1\!\!1})(A−λi11) . Assemble QQQ has the eigenvectors as columns, Λ=diag(λ1,…,λn)\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n)Λ=diag(λ1,…,λn) has the eigenvalues in the same order. Invert Compute Q−1Q^{-1}Q−1 . A 3×33 \times 33×3 eigendecompo…
[Eigenvalues and eigenvectors] What is the diagonalization of a matrix AAA with eigendecomposition A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 ?
Λ=Q−1AQ\boldsymbol{\Lambda = Q^{-1}AQ}Λ=Q−1AQ Multiply A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 by Q−1Q^{-1}Q−1 on the left and by QQQ on the right.
[Eigenvalues and eigenvectors] Find the eigenvalues of A=[1200302−42]A = \begin{bmatrix} 1 & 2 & 0 \\ 0 & 3 & 0 \\ 2 & -4 & 2 \end{bmatrix}A=⎣⎡10223−4002⎦⎤ .
λ1=3, λ2=2, λ3=1\boldsymbol{\lambda_1 = 3, \ \lambda_2 = 2, \ \lambda_3 = 1}λ1=3, λ2=2, λ3=1 Expanding along the third column: det(A−λ1 1)=(2−λ)((1−λ)(3−λ)−0)\det(A - \lambda\mathrm{1\!\!1}) = (2 - \lambda)\big((1 - \lambda)(3 - \lambda) - 0\big)det(A−λ11)=(2−λ)((1−λ)(3−λ)−0) .Three distinct eigenvalues, so AAA is diagonalizable.
[Eigenvalues and eigenvectors] A=[1200302−42]A = \begin{bmatrix} 1 & 2 & 0 \\ 0 & 3 & 0 \\ 2 & -4 & 2 \end{bmatrix}A=⎣⎡10223−4002⎦⎤ has eigenvalues 3, 2, 1.Find an eigenvector for each eigenvalue.
e⃗3=(−1,−1,2)T, e⃗2=(0,0,1)T, e⃗1=(−1,0,2)T\boldsymbol{\vec{e}_3 = (-1, -1, 2)^{\mathsf{T}}, \ \vec{e}_2 = (0, 0, 1)^{\mathsf{T}}, \ \vec{e}_1 = (-1, 0, 2)^{\mathsf{T}}}e3=(−1,−1,2)T, e2=(0,0,1)T, e1=(−1,0,2)T They span the null spaces of A−31 1A - 3\mathrm{1\!\!1}A−311 , A−21 1A - 2\mathrm{1\!\!1}A−211 , A−1 1A - \mathrm{1\!\!1}A−11 .Check: A(−1,−1,2)T=(−3,−3,6)TA(-1, -1, 2)^{\mathsf{T}} = (-3, -3, 6)^{\mathsf{T}}A(−1,−1,2)T=(−3,−3,6)T , A(0,0,1)T=(0,0,2)T\ A(0, 0, 1)^{\mathsf{T}}…
[Eigenvalues and eigenvectors] A=[1200302−42]A = \begin{bmatrix} 1 & 2 & 0 \\ 0 & 3 & 0 \\ 2 & -4 & 2 \end{bmatrix}A=⎣⎡10223−4002⎦⎤ has eigenvectors (−1,−1,2)T,(0,0,1)T,(−1,0,2)T(-1, -1, 2)^{\mathsf{T}}, (0, 0, 1)^{\mathsf{T}}, (-1, 0, 2)^{\mathsf{T}}(−1,−1,2)T,(0,0,1)T,(−1,0,2)T for the eigenvalues 3, 2, 1.Write the eigendecomposition A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 .
Q=[−10−1−100212], Λ=[300020001], Q−1=[0−10201−110]\boldsymbol{Q = \begin{bmatrix} -1 & 0 & -1 \\ -1 & 0 & 0 \\ 2 & 1 & 2 \end{bmatrix}, \ \Lambda = \begin{bmatrix} 3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \ Q^{-1} = \begin{bmatrix} 0 & -1 & 0 \\ 2 & 0 & 1 \\ -1 & 1 & 0 \end{bmatrix}}Q=⎣⎡−1−12001−102⎦⎤, Λ=⎣⎡300020001⎦⎤, Q−1=⎣⎡02−1−101010⎦⎤ Check: Q−1AQ=ΛQ^{-1}AQ = \LambdaQ−1AQ=Λ . The order of the columns of QQQ matches the order of the eigenvalues in Λ\LambdaΛ .
[Eigenvalues and eigenvectors] A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 . Why is Ak=QΛkQ−1A^k = Q\Lambda^k Q^{-1}Ak=QΛkQ−1 ?
In QΛQ−1 QΛQ−1⋯QΛQ−1Q\Lambda Q^{-1} \, Q\Lambda Q^{-1} \cdots Q\Lambda Q^{-1}QΛQ−1QΛQ−1⋯QΛQ−1 every inner Q−1QQ^{-1}QQ−1Q equals 1 1\mathrm{1\!\!1}11 , leaving QΛΛ⋯ΛQ−1Q\Lambda\Lambda\cdots\Lambda Q^{-1}QΛΛ⋯ΛQ−1 . And Λk\Lambda^kΛk is easy: diag(λ1,…,λn)k=diag(λ1k,…,λnk)\operatorname{diag}(\lambda_1, \dots, \lambda_n)^k = \operatorname{diag}(\lambda_1^k, \dots, \lambda_n^k)diag(λ1,…,λn)k=diag(λ1k,…,λnk) .Example: A=[9−2−26]A = \begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix}A=[9−2−26]…
[Eigenvalues and eigenvectors] How many matrix multiplications does computing A7A^7A7 take directly, and how many with A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 ?
Directly 6; with QΛ7Q−1Q\Lambda^7Q^{-1}QΛ7Q−1 only 2, plus powers of the nnn eigenvalues. The same 2 multiplications give A17A^{17}A17 or A777A^{777}A777 : computing powers of AAA reduces to computing powers of its eigenvalues.
[Eigenvalues and eigenvectors] A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 , with the eigenvectors of AAA as the columns of QQQ . Which change of basis does QQQ perform?
Q=Bs[1 1]BλQ = {}_{B_s}[\mathrm{1\!\!1}]_{B_\lambda}Q=Bs[11]Bλ converts coordinates from the eigenbasis BλB_\lambdaBλ to the standard basis BsB_sBs : [v⃗]Bs=Q[v⃗]Bλ[\vec{v}]_{B_s} = Q[\vec{v}]_{B_\lambda}[v]Bs=Q[v]Bλ . Q−1=Bλ[1 1]BsQ^{-1} = {}_{B_\lambda}[\mathrm{1\!\!1}]_{B_s}Q−1=Bλ[11]Bs converts the other way: [v⃗]Bλ=Q−1[v⃗]Bs[\vec{v}]_{B_\lambda} = Q^{-1}[\vec{v}]_{B_s}[v]Bλ=Q−1[v]Bs .Example: [v⃗]Bλ=(v1′,v2′,v3′)T[\vec{v}]_{B_\lambda} = (v_1', v_2', v_3&#x…
[Eigenvalues and eigenvectors] A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 is the eigendecomposition. Read Av⃗=QΛQ−1v⃗A\vec{v} = Q\Lambda Q^{-1}\vec{v}Av=QΛQ−1v from right to left: which three steps does it perform?
Q−1Q^{-1}Q−1 : to the eigenbasis Convert v⃗\vec{v}v from the standard basis to the eigenbasis of AAA . Λ\LambdaΛ : scale In the eigenbasis, the action of AAA is multiplication by the diagonal matrix Λ\LambdaΛ : each coordinate is multiplied by its eigenvalue. QQQ : back to the standard basis Convert the output w⃗\vec{w}w from the eigenbasis to the standard basis. So with respect to its eigenbasis, AAA is the diagonal matrix Λ\LambdaΛ : [w⃗]Bλ=Λ[v⃗]Bλ[\vec{w}]_{B_\lambda} = \Lambda[\vec{v}]_{B_\…
[Eigenvalues and eigenvectors] Av⃗=QΛQ−1v⃗A\vec{v} = Q\Lambda Q^{-1}\vec{v}Av=QΛQ−1v : Q−1Q^{-1}Q−1 converts to the eigenbasis, Λ\LambdaΛ scales, QQQ converts back to the standard basis.Follow the eigenvector e⃗λ1\vec{e}_{\lambda_1}eλ1 (the first column of QQQ ) through the three steps.
e⃗λ1→(1,0,…,0)BλT→(λ1,0,…,0)BλT→λ1e⃗λ1\boldsymbol{\vec{e}_{\lambda_1} \to (1, 0, \dots, 0)^{\mathsf{T}}_{B_\lambda} \to (\lambda_1, 0, \dots, 0)^{\mathsf{T}}_{B_\lambda} \to \lambda_1\vec{e}_{\lambda_1}}eλ1→(1,0,…,0)BλT→(λ1,0,…,0)BλT→λ1eλ1 In the eigenbasis, e⃗λ1\vec{e}_{\lambda_1}eλ1 has coordinates (1,0,…,0)(1, 0, \dots, 0)(1,0,…,0) ; Λ\LambdaΛ multiplies the first coordinate by λ1\lambda_1λ1 ; QQQ turns λ1\lambda_1λ1 times the first basis vector back into λ1e⃗λ1\lambda_1\vec{e}…
[Eigenvalues and eigenvectors] How are det(A)\det(A)det(A) and Tr(A)\operatorname{Tr}(A)Tr(A) related to the eigenvalues λ1,…,λn\lambda_1, \dots, \lambda_nλ1,…,λn of AAA ?
det(A)=λ1λ2⋯λn\boldsymbol{\det(A) = \lambda_1\lambda_2\cdots\lambda_n}det(A)=λ1λ2⋯λn (product), Tr(A)=∑iaii=λ1+⋯+λn\ \boldsymbol{\operatorname{Tr}(A) = \sum_i a_{ii} = \lambda_1 + \dots + \lambda_n} Tr(A)=∑iaii=λ1+⋯+λn (sum) Example: [9−2−26]\begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix}[9−2−26] has eigenvalues 5 and 10: det=54−4=50=5⋅10\det = 54 - 4 = 50 = 5 \cdot 10det=54−4=50=5⋅10 , Tr=9+6=15=5+10\ \operatorname{Tr} = 9 + 6 = 15 = 5 + 10 Tr=9+6=15=5+10 .
[Eigenvalues and eigenvectors] For a diagonalizable A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 : det(A)=∏iλi\det(A) = \prod_i \lambda_idet(A)=∏iλi and Tr(A)=∑iλi\operatorname{Tr}(A) = \sum_i \lambda_iTr(A)=∑iλi .Why do these hold?
∣QΛQ−1∣=∣Q∣∣Λ∣1∣Q∣=∣Λ∣\boldsymbol{|Q\Lambda Q^{-1}| = |Q||\Lambda|\frac{1}{|Q|} = |\Lambda|}∣QΛQ−1∣=∣Q∣∣Λ∣∣Q∣1=∣Λ∣ and Tr(QΛQ−1)=Tr(ΛQ−1Q)=Tr(Λ)\boldsymbol{\operatorname{Tr}(Q\Lambda Q^{-1}) = \operatorname{Tr}(\Lambda Q^{-1}Q) = \operatorname{Tr}(\Lambda)}Tr(QΛQ−1)=Tr(ΛQ−1Q)=Tr(Λ) Uses ∣AB∣=∣A∣∣B∣|AB| = |A||B|∣AB∣=∣A∣∣B∣ , ∣A−1∣=1∣A∣|A^{-1}| = \frac{1}{|A|}∣A−1∣=∣A∣1 and the cyclic property Tr(ABC)=Tr(BCA)\operatorname{Tr}(ABC) = \operatorname{Tr}(BCA)Tr(ABC)=Tr(BCA) . The determinant o…
[Eigenvalues and eigenvectors] What is a similarity transformation of a matrix AAA , and which properties of AAA does it leave unchanged?
A′=PAP−1\boldsymbol{A' = PAP^{-1}}A′=PAP−1 for an invertible PPP (a change of basis). The determinant and the trace are invariant under it. They depend only on the eigenvalues, not on the choice of basis.Example: A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 is a similarity transformation of Λ\LambdaΛ , so detA=detΛ\det A = \det\LambdadetA=detΛ .
[Eigenvalues and eigenvectors] A∈Rn×nA \in \mathbb{R}^{n \times n}A∈Rn×n has eigenvalues λ1,…,λn\lambda_1, \dots, \lambda_nλ1,…,λn . Why is AAA invertible exactly when no λi\lambda_iλi is 0?
∣A∣=λ1λ2⋯λn\boldsymbol{|A| = \lambda_1\lambda_2\cdots\lambda_n}∣A∣=λ1λ2⋯λn , which is nonzero exactly when every λi≠0\lambda_i \neq 0λi=0 . Also directly: λ=0\lambda = 0λ=0 is an eigenvalue ⟺ \iff⟺ some v⃗≠0⃗\vec{v} \neq \vec{0}v=0 has Av⃗=0v⃗=0⃗A\vec{v} = 0\vec{v} = \vec{0}Av=0v=0 ⟺ \iff⟺ N(A)≠{0⃗}\mathcal{N}(A) \neq \{\vec{0}\}N(A)={0} . This links the conditions ∣A∣≠0|A| \neq 0∣A∣=0 and N(A)={0⃗}\mathcal{N}(A) = \{\vec{0}\}N(A)={0} of the invertible matrix theorem.
[Eigenvalues and eigenvectors] When is a matrix AAA normal?
When ATA=AAT\boldsymbol{A^{\mathsf{T}}A = AA^{\mathsf{T}}}ATA=AAT . Example: every symmetric AAA ( AT=AA^{\mathsf{T}} = AAT=A ) is normal: ATA=A2=AATA^{\mathsf{T}}A = A^2 = AA^{\mathsf{T}}ATA=A2=AAT .
[Eigenvalues and eigenvectors] What is special about the eigenvectors of a normal matrix AAA ( ATA=AATA^{\mathsf{T}}A = AA^{\mathsf{T}}ATA=AAT )?
They can be chosen orthonormal: eigenvectors for different eigenvalues are orthogonal, and within one eigenspace they can be chosen orthogonal. Normalized, they form a basis {e^1,…,e^n}\{\hat{e}_1, \dots, \hat{e}_n\}{e^1,…,e^n} with e^i⋅e^j=1\hat{e}_i \cdot \hat{e}_j = 1e^i⋅e^j=1 if i=ji = ji=j and 000 if i≠ji \neq ji=j .Example: [9−2−26]\begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix}[9−2−26] is symmetric, hence normal; its eigenvectors (1,2)T(1, 2)^{\mathsf{T}}(1,2)T and (2,−1)T(2, -1)^{…
[Eigenvalues and eigenvectors] AAA is normal, and OOO has an orthonormal basis of eigenvectors e^1,…,e^n\hat{e}_1, \dots, \hat{e}_ne^1,…,e^n of AAA as its columns. What is the eigendecomposition of AAA ?
A=OΛO−1=OΛOT\boldsymbol{A = O\Lambda O^{-1} = O\Lambda O^{\mathsf{T}}}A=OΛO−1=OΛOT The inverse of OOO is its transpose, so no inverse needs computing: the key advantage of an orthogonal change-of-basis matrix.For real OOO and Λ\LambdaΛ the eigenvalues must be real, as for symmetric matrices; a normal matrix with complex eigenvalues (a rotation by 90°90°90° ) needs complex numbers for this.
[Eigenvalues and eigenvectors] OOO has orthonormal vectors e^1,…,e^n\hat{e}_1, \dots, \hat{e}_ne^1,…,e^n as its columns. Why is OTO=1 1O^{\mathsf{T}}O = \mathrm{1\!\!1}OTO=11 ?
Entry (i,j)(i, j)(i,j) of OTOO^{\mathsf{T}}OOTO is e^i⋅e^j\hat{e}_i \cdot \hat{e}_je^i⋅e^j , which is 1 if i=ji = ji=j and 0 otherwise. Row iii of OTO^{\mathsf{T}}OT is e^i\hat{e}_ie^i . So O−1=OTO^{-1} = O^{\mathsf{T}}O−1=OT .
[Eigenvalues and eigenvectors] Why is B=[3103]B = \begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}B=[3013] not diagonalizable?
λ=3\lambda = 3λ=3 has algebraic multiplicity 2 but geometric multiplicity 1: the null space of B−31 1B - 3\mathrm{1\!\!1}B−311 is spanned by (1,0)T(1, 0)^{\mathsf{T}}(1,0)T alone. BBB has only one linearly independent eigenvector, one short of the two columns a change-of-basis matrix QQQ needs.
[Eigenvalues and eigenvectors] A matrix that does not have a full set of linearly independent eigenvectors is said to have deficient geometric multiplicity, and is not diagonalizable.
Example: [3103]\begin{bmatrix} 3 & 1 \\ 0 & 3 \end{bmatrix}[3013] : eigenvalue 3 twice, but only the eigenvector direction (1,0)T(1, 0)^{\mathsf{T}}(1,0)T .
[Eigenvalues and eigenvectors] How is the matrix exponential eAe^AeA of a square matrix AAA defined?
By the Taylor series of exe^xex with AAA in place of xxx : eA=∑k=0∞Akk!=1 1+A+A22+A33!+⋯\displaystyle\boldsymbol{e^A = \sum_{k=0}^{\infty} \frac{A^k}{k!} = \mathrm{1\!\!1} + A + \frac{A^2}{2} + \frac{A^3}{3!} + \cdots}eA=k=0∑∞k!Ak=11+A+2A2+3!A3+⋯ The first term A0A^0A0 is the identity matrix 1 1\mathrm{1\!\!1}11 .Example: A=0A = \mathbb{0}A=0 gives e0=1 1e^{\mathbb{0}} = \mathrm{1\!\!1}e0=11 .
[Eigenvalues and eigenvectors] A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 with Λ=diag(λ1,…,λn)\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n)Λ=diag(λ1,…,λn) . How can eAe^AeA be computed?
eA=QeΛQ−1\boldsymbol{e^A = Qe^{\Lambda}Q^{-1}}eA=QeΛQ−1 with eΛ=diag(eλ1,…,eλn)\boldsymbol{e^{\Lambda} = \operatorname{diag}(e^{\lambda_1}, \dots, e^{\lambda_n})}eΛ=diag(eλ1,…,eλn) Each term Akk!=QΛkk!Q−1\frac{A^k}{k!} = Q\frac{\Lambda^k}{k!}Q^{-1}k!Ak=Qk!ΛkQ−1 , so QQQ and Q−1Q^{-1}Q−1 factor out of the sum, and ∑kΛkk!\sum_k \frac{\Lambda^k}{k!}∑kk!Λk is diagonal with entries ∑kλikk!=eλi\sum_k \frac{\lambda_i^k}{k!} = e^{\lambda_i}∑kk!λik=eλi .Example: [9−2−26]=Qdiag(5,10)Q−1\begin…
[Eigenvalues and eigenvectors] What is a matrix function F(A)F(A)F(A) defined by a Taylor series, and how is it computed for A=QΛQ−1A = Q\Lambda Q^{-1}A=QΛQ−1 ?
F:Rn×n→Rn×nF : \mathbb{R}^{n \times n} \to \mathbb{R}^{n \times n}F:Rn×n→Rn×n given by the Taylor series of a function fff with AAA in place of xxx ; it is F(A)=Qf(Λ)Q−1\boldsymbol{F(A) = Qf(\Lambda)Q^{-1}}F(A)=Qf(Λ)Q−1 . f(Λ)f(\Lambda)f(Λ) applies fff to each eigenvalue on the diagonal.Example: f(x)=x3f(x) = x^3f(x)=x3 gives A3=Qdiag(λ13,…,λn3)Q−1A^3 = Q\operatorname{diag}(\lambda_1^3, \dots, \lambda_n^3)Q^{-1}A3=Qdiag(λ13,…,λn3)Q−1 .
[Eigenvalues and eigenvectors] Name three applications of eigendecomposition outside linear algebra.
Principal component analysis (statistics) Eigendecomposing the covariance matrix computed from a dataset finds the dominant causes of variation in the data. PageRank (Google) Ranking webpages by "importance" is a search for an eigenvector of a matrix that contains the hyperlinks between webpages. Quantum mechanics The energy of a system is described by the Hamiltonian operator; its eigenvalues are the possible energy levels of the system.
[Special types of matrices] Why do names of special matrices (orthogonal, symmetric, ...) also apply to linear transformations?
Each matrix AAA corresponds to the linear transformation TA(x⃗)=Ax⃗T_A(\vec{x}) = A\vec{x}TA(x)=Ax , so each type of matrix is also a type of linear transformation. Example: Ov⃗=w⃗ ⟺ TO(v⃗)=w⃗O\vec{v} = \vec{w} \iff T_O(\vec{v}) = \vec{w}Ov=w⟺TO(v)=w , so "orthogonal transformation" means TOT_OTO with OOO orthogonal.
[Special types of matrices] What is a diagonal matrix, and what are its eigenvalues?
aij=0a_{ij} = 0aij=0 whenever i≠ji \neq ji=j ; its eigenvalues are the diagonal entries λi=aii\boldsymbol{\lambda_i = a_{ii}}λi=aii . Example: [2007]\begin{bmatrix} 2 & 0 \\ 0 & 7 \end{bmatrix}[2007] has eigenvalues 2 and 7, with eigenvectors (1,0)T(1, 0)^{\mathsf{T}}(1,0)T and (0,1)T(0, 1)^{\mathsf{T}}(0,1)T .
[Special types of matrices] When is a matrix AAA symmetric, and what holds for its eigenvalues and eigenvectors?
AT=A\boldsymbol{A^{\mathsf{T}} = A}AT=A ( aij=ajia_{ij} = a_{ji}aij=aji for all i,ji, ji,j ); its eigenvalues are real and its eigenvectors can be chosen mutually orthogonal. Example: [9−2−26]\begin{bmatrix} 9 & -2 \\ -2 & 6 \end{bmatrix}[9−2−26] has eigenvalues 5 and 10 and orthogonal eigenvectors (1,2)T(1, 2)^{\mathsf{T}}(1,2)T , (2,−1)T(2, -1)^{\mathsf{T}}(2,−1)T .
[Special types of matrices] B∈Rm×nB \in \mathbb{R}^{m \times n}B∈Rm×n is any matrix. Why is BTBB^{\mathsf{T}}BBTB symmetric?
(BTB)T=BT(BT)T=BTB\boldsymbol{(B^{\mathsf{T}}B)^{\mathsf{T}} = B^{\mathsf{T}}(B^{\mathsf{T}})^{\mathsf{T}} = B^{\mathsf{T}}B}(BTB)T=BT(BT)T=BTB Uses (CD)T=DTCT(CD)^{\mathsf{T}} = D^{\mathsf{T}}C^{\mathsf{T}}(CD)T=DTCT .Example: B=[12]B = \begin{bmatrix} 1 & 2 \end{bmatrix}B=[12] gives BTB=[1224]B^{\mathsf{T}}B = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}BTB=[1224] .
[Special types of matrices] What are upper triangular and lower triangular matrices?
Upper: zeros below the diagonal, aij=0a_{ij} = 0aij=0 if i>ji > ji>j . Lower: zeros above the diagonal, aij=0a_{ij} = 0aij=0 if i<ji < ji<j . Example: [1402]\begin{bmatrix} 1 & 4 \\ 0 & 2 \end{bmatrix}[1042] is upper triangular, [1042]\begin{bmatrix} 1 & 0 \\ 4 & 2 \end{bmatrix}[1402] is lower triangular.
[Special types of matrices] What is the identity matrix 1 1n\mathrm{1\!\!1}_n11n , and what are its eigenvectors?
The diagonal matrix with ones on the diagonal, 1 1A=A1 1=A\mathrm{1\!\!1}A = A\mathrm{1\!\!1} = A11A=A11=A ; every nonzero vector is an eigenvector, with eigenvalue 1. Example: 1 13=[100010001]\mathrm{1\!\!1}_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}113=⎣⎡100010001⎦⎤ , and 1 13v⃗=1v⃗\mathrm{1\!\!1}_3\vec{v} = 1\vec{v}113v=1v for every v⃗∈R3\vec{v} \in \mathbb{R}^3v∈R3 .
[Special types of matrices] When is a matrix O∈Rn×nO \in \mathbb{R}^{n \times n}O∈Rn×n orthogonal?
When OOT=1 1=OTO\boldsymbol{OO^{\mathsf{T}} = \mathrm{1\!\!1} = O^{\mathsf{T}}O}OOT=11=OTO , i.e. O−1=OT\boldsymbol{O^{-1} = O^{\mathsf{T}}}O−1=OT . Equivalently, its columns form an orthonormal basis of Rn\mathbb{R}^nRn . OOO is then the change-of-basis matrix from the basis of its columns {e^1,…,e^n}\{\hat{e}_1, \dots, \hat{e}_n\}{e^1,…,e^n} to the standard basis.Example: [0−110]\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}[01−10] : its columns (0,1)T(0, 1)^{\mathsf{T}}(0,1)T and (−1,0…
[Special types of matrices] OOO is orthogonal ( OTO=1 1O^{\mathsf{T}}O = \mathrm{1\!\!1}OTO=11 ). Why is ∥Ov⃗∥=∥v⃗∥\|O\vec{v}\| = \|\vec{v}\|∥Ov∥=∥v∥ ?
∥Ov⃗∥=(Ov⃗)T(Ov⃗)=v⃗TOTOv⃗=v⃗Tv⃗=∥v⃗∥\boldsymbol{\|O\vec{v}\| = \sqrt{(O\vec{v})^{\mathsf{T}}(O\vec{v})} = \sqrt{\vec{v}^{\mathsf{T}}O^{\mathsf{T}}O\vec{v}} = \sqrt{\vec{v}^{\mathsf{T}}\vec{v}} = \|\vec{v}\|}∥Ov∥=(Ov)T(Ov)=vTOTOv=vTv=∥v∥ Uses u⃗⋅v⃗=u⃗Tv⃗\vec{u} \cdot \vec{v} = \vec{u}^{\mathsf{T}}\vec{v}u⋅v=uTv and (AB)T=BTAT(AB)^{\mathsf{T}} = B^{\mathsf{T}}A^{\mathsf{T}}(AB)T=BTAT . So multiplication by an orthogonal matrix is a length preserving operation.
[Special types of matrices] What are the possible eigenvalues and determinants of an orthogonal matrix OOO ?
Eigenvalues have ∣λ∣=1|\lambda| = 1∣λ∣=1 (in general complex, λ=eiθ\lambda = e^{i\theta}λ=eiθ ); detO∈{−1,1}\det O \in \{-1, 1\}detO∈{−1,1} . ∣λ∣=1|\lambda| = 1∣λ∣=1 because OOO preserves lengths: ∥Oe⃗∥=∣λ∣∥e⃗∥\|O\vec{e}\| = |\lambda|\|\vec{e}\|∥Oe∥=∣λ∣∥e∥ must equal ∥e⃗∥\|\vec{e}\|∥e∥ . And (detO)2=det(OTO)=det1 1=1(\det O)^2 = \det(O^{\mathsf{T}}O) = \det\mathrm{1\!\!1} = 1(detO)2=det(OTO)=det11=1 .Example: [0−110]\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}[01−10] has p(λ)=λ2+1p(\l…
[Special types of matrices] What are three special kinds of orthogonal matrices?
Rotations Determinant 1. Example: [0−110]\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}[01−10] , rotation by 90°90°90° counterclockwise. Reflections Determinant −1-1−1 . Example: [100−1]\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}[100−1] , reflection through the xxx -axis. Permutations Change the order of the coefficients of a vector. Example: [0110]\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}[0110] maps (a,b)T(a, b)^{\mathsf{T}}(a,b)T to (b,a)T(b, a)^{\mathsf{T}}(b,a)T .
[Special types of matrices] What is the matrix RθR_\thetaRθ of the counterclockwise rotation by the angle θ\thetaθ in R2\mathbb{R}^2R2 ?
Rθ=[cosθ−sinθsinθcosθ]\boldsymbol{R_\theta = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}}Rθ=[cosθsinθ−sinθcosθ] Its columns are the images of the basis vectors: ı^=(1,0)T↦(cosθ,sinθ)T\hat{\imath} = (1, 0)^{\mathsf{T}} \mapsto (\cos\theta, \sin\theta)^{\mathsf{T}}^=(1,0)T↦(cosθ,sinθ)T and ȷ^=(0,1)T↦(−sinθ,cosθ)T\hat{\jmath} = (0, 1)^{\mathsf{T}} \mapsto (-\sin\theta, \cos\theta)^{\mathsf{T}}^=(0,1)T↦(−sinθ,cosθ)T .Example: θ=90°\theta = 90°θ=90…
[Special types of matrices] What is the matrix of the rotation by the angle θ\thetaθ around the xxx -axis in R3\mathbb{R}^3R3 ?
[1000cosθ−sinθ0sinθcosθ]\boldsymbol{\begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos\theta & -\sin\theta \\ 0 & \sin\theta & \cos\theta \end{bmatrix}}⎣⎡1000cosθsinθ0−sinθcosθ⎦⎤ The rotation takes place in the yzyzyz -plane, so the xxx -component of the vector is unchanged.
[Special types of matrices] What are the determinant and the eigenvalues of a rotation matrix?
Determinant 1; eigenvalues are complex numbers of magnitude 1. Example: RθR_\thetaRθ in R2\mathbb{R}^2R2 has det=cos2θ+sin2θ=1\det = \cos^2\theta + \sin^2\theta = 1det=cos2θ+sin2θ=1 and eigenvalues cosθ±isinθ=e±iθ\cos\theta \pm i\sin\theta = e^{\pm i\theta}cosθ±isinθ=e±iθ .
[Special types of matrices] What is the matrix of the reflection through the line with direction vector (cosθ,sinθ)(\cos\theta, \sin\theta)(cosθ,sinθ) in R2\mathbb{R}^2R2 ?
R=[cos2θsin2θsin2θ−cos2θ]\boldsymbol{R = \begin{bmatrix} \cos 2\theta & \sin 2\theta \\ \sin 2\theta & -\cos 2\theta \end{bmatrix}}R=[cos2θsin2θsin2θ−cos2θ] detR=−cos22θ−sin22θ=−1\det R = -\cos^2 2\theta - \sin^2 2\theta = -1detR=−cos22θ−sin22θ=−1 : an orthogonal matrix with determinant −1-1−1 is called mirrored orthogonal.Example: θ=0\theta = 0θ=0 (the xxx -axis) gives [100−1]\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}[100−1] , so (a,b)T↦(a,−b)T(a, b)^{\mathsf{T}} \mapsto (a, -b)^…
[Special types of matrices] Why does every reflection matrix have the eigenvalue −1-1−1 ?
A vector perpendicular to the axis of reflection is mapped to its negative. Vectors along the axis are unchanged, eigenvalue 1.Example: [100−1]\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}[100−1] (reflection through the xxx -axis) maps (0,1)T(0, 1)^{\mathsf{T}}(0,1)T to (0,−1)T(0, -1)^{\mathsf{T}}(0,−1)T and (1,0)T(1, 0)^{\mathsf{T}}(1,0)T to itself.
[Special types of matrices] What is an n×nn \times nn×n permutation matrix?
A matrix with nnn ones, one in each row and each column, and zeros elsewhere; multiplying by it changes the order of the coefficients of a vector. It is orthogonal: its columns are the standard basis vectors in another order.Example: π:e^1→e^1′, e^2→e^3′, e^3→e^2′\pi: \hat{e}_1 \to \hat{e}_1', \ \hat{e}_2 \to \hat{e}_3', \ \hat{e}_3 \to \hat{e}_2'π:e^1→e^1′, e^2→e^3′, e^3→e^2′ has Mπ=[100001010]M_\pi = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}Mπ=⎣⎡…
[Special types of matrices] What is the sign of a permutation π\piπ , and when is π\piπ even or odd?
The sign is det(Mπ)∈{1,−1}\det(M_\pi) \in \{1, -1\}det(Mπ)∈{1,−1} : π\piπ is even if det(Mπ)=+1\det(M_\pi) = +1det(Mπ)=+1 , odd if det(Mπ)=−1\det(M_\pi) = -1det(Mπ)=−1 . MπM_\piMπ is the permutation matrix of π\piπ .Example: [100001010]\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}⎣⎡100001010⎦⎤ swaps the last two coefficients and has determinant −1-1−1 : odd.
[Special types of matrices] When is a matrix P∈Rn×nP \in \mathbb{R}^{n \times n}P∈Rn×n positive semidefinite, and when positive definite?
Semidefinite: v⃗TPv⃗≥0\boldsymbol{\vec{v}^{\mathsf{T}}P\vec{v} \ge 0}vTPv≥0 for all v⃗∈Rn\vec{v} \in \mathbb{R}^nv∈Rn . Definite: v⃗TPv⃗>0\boldsymbol{\vec{v}^{\mathsf{T}}P\vec{v} > 0}vTPv>0 for all v⃗≠0⃗\vec{v} \neq \vec{0}v=0 . v⃗=0⃗\vec{v} = \vec{0}v=0 always gives 0, so it is excluded from the strict inequality.Example: [1000]\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}[1000] gives v⃗TPv⃗=v12≥0\vec{v}^{\mathsf{T}}P\vec{v} = v_1^2 \ge 0vTPv=v12≥0 : semidefinite, not definite ( v⃗=(0,1)T\v…
[Special types of matrices] What do the eigenvalues of a positive semidefinite and of a positive definite (symmetric) matrix satisfy?
Semidefinite: all λi≥0\lambda_i \ge 0λi≥0 . Definite: all λi>0\lambda_i > 0λi>0 . For an eigenvector, e⃗TPe⃗=λ∥e⃗∥2\vec{e}^{\mathsf{T}}P\vec{e} = \lambda\|\vec{e}\|^2eTPe=λ∥e∥2 , so the sign of λ\lambdaλ is the sign of e⃗TPe⃗\vec{e}^{\mathsf{T}}P\vec{e}eTPe .This needs PPP symmetric: the 90°90°90° rotation matrix has v⃗TPv⃗=0\vec{v}^{\mathsf{T}}P\vec{v} = 0vTPv=0 for all v⃗\vec{v}v , yet eigenvalues ±i\pm i±i .
[Special types of matrices] What is the defining property of a projection matrix Π\PiΠ ?
Π2=Π\boldsymbol{\Pi^2 = \Pi}Π2=Π : applying it several times gives the same result as applying it once ( Π=Π2=Π3=⋯\Pi = \Pi^2 = \Pi^3 = \cdotsΠ=Π2=Π3=⋯ ). Example: projection onto the xxx -axis, [1000]\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}[1000] , maps (a,b)T(a, b)^{\mathsf{T}}(a,b)T to (a,0)T(a, 0)^{\mathsf{T}}(a,0)T , and again to (a,0)T(a, 0)^{\mathsf{T}}(a,0)T .
[Special types of matrices] ΠS\Pi_SΠS is the projection onto a subspace SSS . What are its eigenvalues, and which vectors are the eigenvectors?
λ=1\lambda = 1λ=1 : the vectors of SSS (left unchanged). λ=0\lambda = 0λ=0 : the vectors of the orthogonal complement S⊥S^\perpS⊥ , which is the null space of ΠS\Pi_SΠS . Only 0 and 1 are possible: Πv⃗=λv⃗\Pi\vec{v} = \lambda\vec{v}Πv=λv and Π2=Π\Pi^2 = \PiΠ2=Π give λ2v⃗=λv⃗\lambda^2\vec{v} = \lambda\vec{v}λ2v=λv , so λ2=λ\lambda^2 = \lambdaλ2=λ .Example: [1000]\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}[1000] (onto the xxx -axis): (1,0)T(1, 0)^{\mathsf{T}}(1,0)T has eigenvalue 1, (0,1)T(0,…
[Special types of matrices] A∈Rn×nA \in \mathbb{R}^{n \times n}A∈Rn×n is normal ( ATA=AATA^{\mathsf{T}}A = AA^{\mathsf{T}}ATA=AAT ). Which properties follow?
Same eigenvectors as ATA^{\mathsf{T}}AT v⃗\vec{v}v is an eigenvector of AAA if and only if v⃗\vec{v}v is an eigenvector of ATA^{\mathsf{T}}AT . Dot products (Av⃗)⋅(Aw⃗)=v⃗TATAw⃗=v⃗TAATw⃗=(ATv⃗)⋅(ATw⃗)(A\vec{v}) \cdot (A\vec{w}) = \vec{v}^{\mathsf{T}}A^{\mathsf{T}}A\vec{w} = \vec{v}^{\mathsf{T}}AA^{\mathsf{T}}\vec{w} = (A^{\mathsf{T}}\vec{v}) \cdot (A^{\mathsf{T}}\vec{w})(Av)⋅(Aw)=vTATAw=vTAATw=(ATv)⋅(ATw) for all v⃗,w⃗\vec{v}, \vec{w}v,w . Orthogonal eigenvectors A full set of linearly independ…
[Special types of matrices] Why are orthogonal and symmetric matrices normal?
Orthogonal: OTO=1 1=OOT\boldsymbol{O^{\mathsf{T}}O = \mathrm{1\!\!1} = OO^{\mathsf{T}}}OTO=11=OOT . Symmetric: ATA=A2=AAT\boldsymbol{A^{\mathsf{T}}A = A^2 = AA^{\mathsf{T}}}ATA=A2=AAT . Normal means ATA=AATA^{\mathsf{T}}A = AA^{\mathsf{T}}ATA=AAT .
[Special types of matrices] The complex-coefficient analogues of orthogonal and symmetric matrices are called unitary and Hermitian matrices.
They are defined with the conjugate transpose †\dagger† (transpose and complex conjugation) in place of T\mathsf{T}T ; a unitary matrix with real entries is orthogonal, a Hermitian one is symmetric.
[Special types of matrices] Which constraint on the eigenvalues (or the determinant) goes with each special type of matrix?
Invertible All eigenvalues nonzero. Symmetric (and Hermitian) Real eigenvalues. Positive definite / semidefinite Positive / nonnegative eigenvalues. Projections Eigenvalues 0 or 1. Rotations Complex eigenvalues of magnitude 1. Reflections Eigenvalues 1 and −1-1−1 . Permutations Determinant 1 or −1-1−1 . Normal matrices have a full set of eigenvectors, so they are diagonalizable. A concept map of these relations:
[Abstract vector spaces] What four things make up an abstract vector space (V,F,+,⋅)(V, F, +, \cdot)(V,F,+,⋅) ?
Set of vectors VVV The vector-like objects u,v,…u, v, \dotsu,v,… Example: V=R2×2V = \mathbb{R}^{2 \times 2}V=R2×2 , the real 2×22 \times 22×2 matrices. Field of scalars FFF The numbers used for scaling, usually F=RF = \mathbb{R}F=R . Example: F=RF = \mathbb{R}F=R or F=CF = \mathbb{C}F=C . Addition +++ A rule giving u+v∈Vu + v \in Vu+v∈V for u,v∈Vu, v \in Vu,v∈V . Example: matrix addition, (A+B)ij=aij+bij(A + B)_{ij} = a_{ij} + b_{ij}(A+B)ij=aij+bij . Scalar multiplication ⋅\cdot⋅ A rule givi…
[Abstract vector spaces] What is a field?
A set of number-like objects for which addition, subtraction, multiplication and division are defined. Example: R\mathbb{R}R and C\mathbb{C}C are fields. The scalars of a vector space come from a field.
[Abstract vector spaces] Which four vector space axioms concern addition alone (for all u,v,w∈Vu, v, w \in Vu,v,w∈V )?
Associativity u+(v+w)=(u+v)+wu + (v + w) = (u + v) + wu+(v+w)=(u+v)+w Example: (1,0)+((0,1)+(2,2))=((1,0)+(0,1))+(2,2)=(3,3)(1, 0) + \big((0, 1) + (2, 2)\big) = \big((1, 0) + (0, 1)\big) + (2, 2) = (3, 3)(1,0)+((0,1)+(2,2))=((1,0)+(0,1))+(2,2)=(3,3) Commutativity u+v=v+uu + v = v + uu+v=v+u Example: (1,2)+(3,0)=(3,0)+(1,2)=(4,2)(1, 2) + (3, 0) = (3, 0) + (1, 2) = (4, 2)(1,2)+(3,0)=(3,0)+(1,2)=(4,2) Zero vector There is a 0∈V0 \in V0∈V with u+0=0+u=uu + 0 = 0 + u = uu+0=0+u=u for all uuu . Examp…
[Abstract vector spaces] Which four vector space axioms involve scalars (for all α,β∈F\alpha, \beta \in Fα,β∈F , u,v∈Vu, v \in Vu,v∈V )?
Distributivity I α(u+v)=αu+αv\alpha(u + v) = \alpha u + \alpha vα(u+v)=αu+αv Example: 2((1,0)+(0,1))=(2,0)+(0,2)=(2,2)2\big((1, 0) + (0, 1)\big) = (2, 0) + (0, 2) = (2, 2)2((1,0)+(0,1))=(2,0)+(0,2)=(2,2) Distributivity II (α+β)u=αu+βu(\alpha + \beta) u = \alpha u + \beta u(α+β)u=αu+βu Example: (2+3)(1,1)=(2,2)+(3,3)=(5,5)(2 + 3)(1, 1) = (2, 2) + (3, 3) = (5, 5)(2+3)(1,1)=(2,2)+(3,3)=(5,5) Associativity of scalar multiplication α(βu)=(αβ)u\alpha(\beta u) = (\alpha\beta) uα(βu)=(αβ)u Example: 2(3…
[Abstract vector spaces] What is the standard basis of Rm×n\mathbb{R}^{m \times n}Rm×n , and what is the dimension of Rm×n\mathbb{R}^{m \times n}Rm×n ?
The mnmnmn matrices with a single 1 (in row iii , column jjj ) and 0 everywhere else, so the dimension is mnmnmn . Example: for R2×2\mathbb{R}^{2 \times 2}R2×2 : e1=[1000],e2=[0100],e3=[0010],e4=[0001]e_1 = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, e_2 = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}, e_3 = \begin{bmatrix} 0 & 0 \\ 1 & 0 \end{bmatrix}, e_4 = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}e1=[1000],e2=[0010],e3=[0100],e4=[0001] [a11a12a21a22]=a11e1+a12e2+a21e3+a22e4\b…
[Abstract vector spaces] In what precise sense is a matrix A∈R2×2A \in \mathbb{R}^{2 \times 2}A∈R2×2 a vector of R4\mathbb{R}^4R4 ?
There is an isomorphism [a11a12a21a22]↔(a11,a12,a21,a22)Bs\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \leftrightarrow (a_{11}, a_{12}, a_{21}, a_{22})_{B_s}[a11a21a12a22]↔(a11,a12,a21,a22)Bs , the coefficients with respect to the standard basis BsB_sBs . Adding and scaling matrices gives the same result as adding and scaling their coefficient vectors.Example: [1234]+[1001]=[2235]\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{…
[Abstract vector spaces] Give a basis and the dimension of the space S(2,2)={A∈R2×2∣A=AT}\mathbb{S}(2, 2) = \{A \in \mathbb{R}^{2 \times 2} \mid A = A^T\}S(2,2)={A∈R2×2∣A=AT} of symmetric 2×22 \times 22×2 matrices.
v1=[1000], v2=[0110], v3=[0001]v_1 = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, \ v_2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, \ v_3 = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}v1=[1000], v2=[0110], v3=[0001] ; dimension 3. [abbc]=av1+bv2+cv3\begin{bmatrix} a & b \\ b & c \end{bmatrix} = a v_1 + b v_2 + c v_3[abbc]=av1+bv2+cv3 . The constraint a12=a21a_{12} = a_{21}a12=a21 removes one of the 4 free parameters of a 2×22 \times 22×2 matrix.
[Abstract vector spaces] What is the vector space Pn(x)P_n(x)Pn(x) , and what is its dimension?
The polynomials of degree at most nnn with real coefficients; dimension n+1n + 1n+1 . Basis 1,x,x2,…,xn1, x, x^2, \dots, x^n1,x,x2,…,xn : each polynomial a0+a1x+⋯+anxna_0 + a_1 x + \dots + a_n x^na0+a1x+⋯+anxn has n+1n + 1n+1 coefficients.Example: in P2(x)P_2(x)P2(x) , 3−x+2x2↔(3,−1,2)3 - x + 2x^2 \leftrightarrow (3, -1, 2)3−x+2x2↔(3,−1,2) .
[Abstract vector spaces] How are two polynomials of Pn(x)P_n(x)Pn(x) added, and how is a polynomial scaled?
Coefficient by coefficient: (a0+⋯+anxn)+(b0+⋯+bnxn)=(a0+b0)+⋯+(an+bn)xn(a_0 + \dots + a_n x^n) + (b_0 + \dots + b_n x^n) = (a_0 + b_0) + \dots + (a_n + b_n) x^n(a0+⋯+anxn)+(b0+⋯+bnxn)=(a0+b0)+⋯+(an+bn)xn and αp=αa0+⋯+αanxn\alpha p = \alpha a_0 + \dots + \alpha a_n x^nαp=αa0+⋯+αanxn . Example: (1+2x)+(3−x+x2)=4+x+x2(1 + 2x) + (3 - x + x^2) = 4 + x + x^2(1+2x)+(3−x+x2)=4+x+x2 , and 2(1+2x)=2+4x2(1 + 2x) = 2 + 4x2(1+2x)=2+4x .
[Abstract vector spaces] In the vector space of functions f:R→Rf : \mathbb{R} \to \mathbb{R}f:R→R , how are addition and scalar multiplication defined, and what is the dimension?
Pointwise: (f+g)(x)=f(x)+g(x)(f + g)(x) = f(x) + g(x)(f+g)(x)=f(x)+g(x) , (αf)(x)=αf(x)(\alpha f)(x) = \alpha f(x)(αf)(x)=αf(x) . The space is infinite-dimensional. For every nnn , the functions 1,x,…,xn1, x, \dots, x^n1,x,…,xn are linearly independent, so no finite basis exists.Example: for f(x)=x2f(x) = x^2f(x)=x2 and g(x)=3xg(x) = 3xg(x)=3x : (f+2g)(1)=1+6=7(f + 2g)(1) = 1 + 6 = 7(f+2g)(1)=1+6=7 .
[Abstract inner product spaces] What is an abstract inner product on a real vector space VVV ?
An operation ⟨⋅,⋅⟩:V×V→R\langle \cdot, \cdot \rangle : V \times V \to \mathbb{R}⟨⋅,⋅⟩:V×V→R that is symmetric, linear and positive semidefinite. It generalizes the dot product ⟨u⃗,v⃗⟩=u⃗⋅v⃗=∑iuivi=u⃗Tv⃗\langle \vec{u}, \vec{v} \rangle = \vec{u} \cdot \vec{v} = \sum_i u_i v_i = \vec{u}^T \vec{v}⟨u,v⟩=u⋅v=∑iuivi=uTv of Rn\mathbb{R}^nRn . A vector space with an inner product is an inner product space.
[Abstract inner product spaces] Which three criteria must an inner product ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle⟨⋅,⋅⟩ satisfy (for all u,v,v1,v2∈Vu, v, v_1, v_2 \in Vu,v,v1,v2∈V , α,β∈R\alpha, \beta \in \mathbb{R}α,β∈R )?
Symmetric ⟨u,v⟩=⟨v,u⟩\langle u, v \rangle = \langle v, u \rangle⟨u,v⟩=⟨v,u⟩ Example: (1,2)⋅(3,4)=(3,4)⋅(1,2)=11(1, 2) \cdot (3, 4) = (3, 4) \cdot (1, 2) = 11(1,2)⋅(3,4)=(3,4)⋅(1,2)=11 Linear ⟨u,αv1+βv2⟩=α⟨u,v1⟩+β⟨u,v2⟩\langle u, \alpha v_1 + \beta v_2 \rangle = \alpha \langle u, v_1 \rangle + \beta \langle u, v_2 \rangle⟨u,αv1+βv2⟩=α⟨u,v1⟩+β⟨u,v2⟩ Example: (1,0)⋅(2(1,1)+3(0,1))=(1,0)⋅(2,5)=2=2⋅1+3⋅0(1, 0) \cdot \big(2(1, 1) + 3(0, 1)\big) = (1, 0) \cdot (2, 5) = 2 = 2 \cdot 1 + 3 \cdot 0(1,…
[Abstract inner product spaces] When are two vectors u,vu, vu,v of an abstract inner product space orthogonal?
When ⟨u,v⟩=0\langle u, v \rangle = 0⟨u,v⟩=0 . An angle may not make sense (what is the angle between two polynomials?), but this notion of perpendicular exists in every inner product space.Example: with ⟨f,g⟩=∫−11f(t)g(t) dt\langle f, g \rangle = \int_{-1}^{1} f(t) g(t) \, dt⟨f,g⟩=∫−11f(t)g(t)dt , the polynomials 111 and xxx are orthogonal: ∫−11t dt=0\int_{-1}^{1} t \, dt = 0∫−11tdt=0 .
[Abstract inner product spaces] u⃗,v⃗∈Rn\vec{u}, \vec{v} \in \mathbb{R}^nu,v∈Rn are nonzero with u⃗⋅v⃗=0\vec{u} \cdot \vec{v} = 0u⋅v=0 . Why are they at a right angle?
u⃗⋅v⃗=∥u⃗∥∥v⃗∥cosθ\vec{u} \cdot \vec{v} = \|\vec{u}\| \|\vec{v}\| \cos\thetau⋅v=∥u∥∥v∥cosθ , so cosθ=0\cos\theta = 0cosθ=0 , which holds only for θ=90∘\theta = 90^\circθ=90∘ or 270∘270^\circ270∘ . θ\thetaθ is the angle between u⃗\vec{u}u and v⃗\vec{v}v .
[Abstract inner product spaces] How does an inner product define the norm ∥u∥\|u\|∥u∥ (length) of an abstract vector uuu ?
∥u∥=⟨u,u⟩\boldsymbol{\|u\| = \sqrt{\langle u, u \rangle}}∥u∥=⟨u,u⟩ Example: with ⟨f,g⟩=∫−11f(t)g(t) dt\langle f, g \rangle = \int_{-1}^{1} f(t) g(t) \, dt⟨f,g⟩=∫−11f(t)g(t)dt : ∥x∥=∫−11t2 dt=2/3\|x\| = \sqrt{\int_{-1}^{1} t^2 \, dt} = \sqrt{2/3}∥x∥=∫−11t2dt=2/3 .
[Abstract inner product spaces] How does an inner product define the distance d(u,v)d(u, v)d(u,v) between two abstract vectors?
d(u,v)=∥u−v∥=⟨u−v,u−v⟩\boldsymbol{d(u, v) = \|u - v\| = \sqrt{\langle u - v, u - v \rangle}}d(u,v)=∥u−v∥=⟨u−v,u−v⟩ In Rn\mathbb{R}^nRn : the distance between points ppp and qqq is the length of the vector from ppp to qqq , ∥q−p∥\|q - p\|∥q−p∥ .Example: d((1,2),(4,6))=∥(−3,−4)∥=5d\big((1, 2), (4, 6)\big) = \|(-3, -4)\| = 5d((1,2),(4,6))=∥(−3,−4)∥=5 .
[Abstract inner product spaces] Which four properties does every norm ∥⋅∥\|\cdot\|∥⋅∥ satisfy (for vectors u,vu, vu,v and scalar kkk )?
Nonnegative ∥v∥≥0\|v\| \ge 0∥v∥≥0 , with equality if and only if v=0v = 0v=0 . Example: ∥(3,4)∥=5\|(3, 4)\| = 5∥(3,4)∥=5 Scaling ∥kv∥=∣k∣ ∥v∥\|kv\| = |k| \, \|v\|∥kv∥=∣k∣∥v∥ Example: ∥−2(3,4)∥=∥(−6,−8)∥=10=∣−2∣⋅5\|-2(3, 4)\| = \|(-6, -8)\| = 10 = |-2| \cdot 5∥−2(3,4)∥=∥(−6,−8)∥=10=∣−2∣⋅5 Triangle inequality ∥u+v∥≤∥u∥+∥v∥\|u + v\| \le \|u\| + \|v\|∥u+v∥≤∥u∥+∥v∥ Example: ∥(1,0)+(0,1)∥=2≤1+1\|(1, 0) + (0, 1)\| = \sqrt{2} \le 1 + 1∥(1,0)+(0,1)∥=2≤1+1 Cauchy–Schwarz inequality ∣⟨u,v⟩∣≤∥u∥ ∥v∥|\lang…
[Abstract inner product spaces] Which two properties does a distance d(u,v)=∥u−v∥d(u, v) = \|u - v\|d(u,v)=∥u−v∥ satisfy?
Symmetric d(u,v)=d(v,u)d(u, v) = d(v, u)d(u,v)=d(v,u) Example: d((1,2),(4,6))=d((4,6),(1,2))=5d\big((1, 2), (4, 6)\big) = d\big((4, 6), (1, 2)\big) = 5d((1,2),(4,6))=d((4,6),(1,2))=5 Nonnegative d(u,v)≥0d(u, v) \ge 0d(u,v)≥0 , with equality if and only if u=vu = vu=v . Example: d(u,u)=∥0∥=0d(u, u) = \|0\| = 0d(u,u)=∥0∥=0
[Abstract inner product spaces] What is the Hilbert–Schmidt inner product ⟨A,B⟩HS\langle A, B \rangle_{\mathrm{HS}}⟨A,B⟩HS of two real matrices?
⟨A,B⟩HS=Tr(ATB)\boldsymbol{\langle A, B \rangle_{\mathrm{HS}} = \operatorname{Tr}(A^T B)}⟨A,B⟩HS=Tr(ATB) , which equals ∑i,jaijbij\sum_{i,j} a_{ij} b_{ij}∑i,jaijbij . Example: A=[1201],B=[1031]A = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}, B = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}A=[1021],B=[1301] : 1⋅1+2⋅0+0⋅3+1⋅1=2\ 1 \cdot 1 + 2 \cdot 0 + 0 \cdot 3 + 1 \cdot 1 = 2 1⋅1+2⋅0+0⋅3+1⋅1=2 .
[Abstract inner product spaces] ⟨A,B⟩HS=Tr(ATB)=∑i,jaijbij\langle A, B \rangle_{\mathrm{HS}} = \operatorname{Tr}(A^T B) = \sum_{i,j} a_{ij} b_{ij}⟨A,B⟩HS=Tr(ATB)=∑i,jaijbij Is the basis v1=[1000],v2=[0110],v3=[0001]v_1 = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, v_2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, v_3 = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}v1=[1000],v2=[0110],v3=[0001] of the symmetric 2×22 \times 22×2 matrices orthogonal for ⟨⋅,⋅⟩HS\langle \cdot, \cdot…
Yes: ⟨v1,v2⟩HS=⟨v1,v3⟩HS=⟨v2,v3⟩HS=0\langle v_1, v_2 \rangle_{\mathrm{HS}} = \langle v_1, v_3 \rangle_{\mathrm{HS}} = \langle v_2, v_3 \rangle_{\mathrm{HS}} = 0⟨v1,v2⟩HS=⟨v1,v3⟩HS=⟨v2,v3⟩HS=0 . No two of the matrices have a nonzero entry in the same position, so every product aijbija_{ij} b_{ij}aijbij is 0.
[Abstract inner product spaces] What is the Hilbert–Schmidt norm ∥A∥HS\|A\|_{\mathrm{HS}}∥A∥HS of a real matrix AAA ?
∥A∥HS=Tr(ATA)=∑i,j∣aij∣2\boldsymbol{\|A\|_{\mathrm{HS}} = \sqrt{\operatorname{Tr}(A^T A)} = \sqrt{\textstyle\sum_{i,j} |a_{ij}|^2}}∥A∥HS=Tr(ATA)=∑i,j∣aij∣2 It is the norm induced by ⟨A,B⟩HS=Tr(ATB)\langle A, B \rangle_{\mathrm{HS}} = \operatorname{Tr}(A^T B)⟨A,B⟩HS=Tr(ATB) , and measures the "length" of a matrix.Example: ∥[1220]∥HS=1+4+4+0=3\left\| \begin{bmatrix} 1 & 2 \\ 2 & 0 \end{bmatrix} \right\|_{\mathrm{HS}} = \sqrt{1 + 4 + 4 + 0} = 3∥∥[1220]∥∥HS=1+4+4+0=3
[Abstract inner product spaces] v1=[1000],v2=[0110],v3=[0001]v_1 = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, v_2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, v_3 = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}v1=[1000],v2=[0110],v3=[0001] is an orthogonal basis of the symmetric 2×22 \times 22×2 matrices for ⟨A,B⟩HS=Tr(ATB)\langle A, B \rangle_{\mathrm{HS}} = \operatorname{Tr}(A^T B)⟨A,B⟩HS=Tr(ATB) .Turn it into an orthonormal basis.
v^1=v1, v^2=12v2, v^3=v3\boldsymbol{\hat{v}_1 = v_1, \ \hat{v}_2 = \tfrac{1}{\sqrt{2}} v_2, \ \hat{v}_3 = v_3}v^1=v1, v^2=21v2, v^3=v3 ∥v2∥HS=02+12+12+02=2\|v_2\|_{\mathrm{HS}} = \sqrt{0^2 + 1^2 + 1^2 + 0^2} = \sqrt{2}∥v2∥HS=02+12+12+02=2 , while v1v_1v1 and v3v_3v3 already have norm 1.
[Abstract inner product spaces] What is the standard inner product of two functions f(t)f(t)f(t) and g(t)g(t)g(t) ?
⟨f,g⟩=∫−∞∞f(t)g(t) dt\boldsymbol{\langle f, g \rangle = \int_{-\infty}^{\infty} f(t) g(t) \, dt}⟨f,g⟩=∫−∞∞f(t)g(t)dt The continuous version of u⃗⋅v⃗=∑iuivi\vec{u} \cdot \vec{v} = \sum_i u_i v_iu⋅v=∑iuivi : an integral instead of a sum. It measures the overlap between fff and ggg .Example: on [−1,1][-1, 1][−1,1] instead: ⟨1,x2⟩=∫−11t2 dt=23\langle 1, x^2 \rangle = \int_{-1}^{1} t^2 \, dt = \tfrac{2}{3}⟨1,x2⟩=∫−11t2dt=32 .
[Abstract inner product spaces] What are the first four Legendre polynomials P0,…,P3P_0, \dots, P_3P0,…,P3 , and what property do they have?
P0=1, P1=x, P2=12(3x2−1), P3=12(5x3−3x)\boldsymbol{P_0 = 1, \ P_1 = x, \ P_2 = \tfrac12(3x^2 - 1), \ P_3 = \tfrac12(5x^3 - 3x)}P0=1, P1=x, P2=21(3x2−1), P3=21(5x3−3x) : mutually orthogonal for ⟨f,g⟩=∫−11f(t)g(t) dt\langle f, g \rangle = \int_{-1}^{1} f(t) g(t) \, dt⟨f,g⟩=∫−11f(t)g(t)dt . Example: ⟨P0,P2⟩=12∫−11(3t2−1) dt=12(2−2)=0\langle P_0, P_2 \rangle = \tfrac12 \int_{-1}^{1} (3t^2 - 1) \, dt = \tfrac12 (2 - 2) = 0⟨P0,P2⟩=21∫−11(3t2−1)dt=21(2−2)=0 Example: ⟨P1,P3⟩=12∫−11(5t4−3t2)…
[Abstract inner product spaces] ⟨f,g⟩=∫−11f(t)g(t) dt\langle f, g \rangle = \int_{-1}^{1} f(t) g(t) \, dt⟨f,g⟩=∫−11f(t)g(t)dt Why are an even polynomial and an odd polynomial always orthogonal for this inner product?
Their product is an odd function, and the integral of an odd function over [−1,1][-1, 1][−1,1] is 0. Example: ⟨x,12(3x2−1)⟩=12∫−11(3t3−t) dt=0\langle x, \tfrac12(3x^2 - 1) \rangle = \tfrac12 \int_{-1}^{1} (3t^3 - t) \, dt = 0⟨x,21(3x2−1)⟩=21∫−11(3t3−t)dt=0
[Abstract inner product spaces] What is the generalized dot product ⟨x⃗,y⃗⟩M\langle \vec{x}, \vec{y} \rangle_M⟨x,y⟩M for a matrix MMM , and what must MMM be?
⟨x⃗,y⃗⟩M=x⃗TMy⃗\boldsymbol{\langle \vec{x}, \vec{y} \rangle_M = \vec{x}^T M \vec{y}}⟨x,y⟩M=xTMy , with MMM symmetric and positive semidefinite. The ordinary dot product is x⃗TIy⃗\vec{x}^T I \vec{y}xTIy .Example: M=[2001]M = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}M=[2001] : ⟨(1,1),(1,−1)⟩M=2⋅1⋅1+1⋅1⋅(−1)=1\langle (1, 1), (1, -1) \rangle_M = 2 \cdot 1 \cdot 1 + 1 \cdot 1 \cdot (-1) = 1⟨(1,1),(1,−1)⟩M=2⋅1⋅1+1⋅1⋅(−1)=1 .
[Abstract inner product spaces] In the generalized dot product ⟨x⃗,y⃗⟩M=x⃗TMy⃗\langle \vec{x}, \vec{y} \rangle_M = \vec{x}^T M \vec{y}⟨x,y⟩M=xTMy , the matrix MMM is called the metric.
It encodes how much each component of the vectors contributes to the inner product.
[Abstract inner product spaces] ⟨x⃗,y⃗⟩M=x⃗TMy⃗\langle \vec{x}, \vec{y} \rangle_M = \vec{x}^T M \vec{y}⟨x,y⟩M=xTMy Why must MMM be symmetric and positive semidefinite?
Symmetric gives ⟨u,v⟩=⟨v,u⟩\langle u, v \rangle = \langle v, u \rangle⟨u,v⟩=⟨v,u⟩ ; positive semidefinite gives ⟨u,u⟩=u⃗TMu⃗≥0\langle u, u \rangle = \vec{u}^T M \vec{u} \ge 0⟨u,u⟩=uTMu≥0 . For " ⟨u,u⟩=0\langle u, u \rangle = 0⟨u,u⟩=0 only when u=0u = 0u=0 ", MMM must even be positive definite.
[Abstract inner product spaces] ⟨x⃗,y⃗⟩M=x⃗TMy⃗\langle \vec{x}, \vec{y} \rangle_M = \vec{x}^T M \vec{y}⟨x,y⟩M=xTMy , and TA(u⃗)=Au⃗T_A(\vec{u}) = A\vec{u}TA(u)=Au is the linear transformation of a matrix AAA .What is ⟨u⃗,v⃗⟩M\langle \vec{u}, \vec{v} \rangle_M⟨u,v⟩M when M=ATAM = A^T AM=ATA ?
The ordinary dot product of the outputs: ⟨u⃗,v⃗⟩M=(Au⃗)⋅(Av⃗)=TA(u⃗)⋅TA(v⃗)\langle \vec{u}, \vec{v} \rangle_M = (A\vec{u}) \cdot (A\vec{v}) = T_A(\vec{u}) \cdot T_A(\vec{v})⟨u,v⟩M=(Au)⋅(Av)=TA(u)⋅TA(v) . u⃗TATAv⃗=(Au⃗)T(Av⃗)\vec{u}^T A^T A \vec{v} = (A\vec{u})^T (A\vec{v})uTATAv=(Au)T(Av) . Every ATAA^T AATA is symmetric and positive semidefinite.Example: A=[2001]A = \begin{bmatrix} \sqrt2 & 0 \\ 0 & 1 \end{bmatrix}A=[2001] gives M=[2001]M = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}M=[…
[Abstract inner product spaces] What is the cosine similarity of two vectors w⃗i,w⃗j\vec{w}_i, \vec{w}_jwi,wj ?
⟨w⃗i,w⃗j⟩∥w⃗i∥ ∥w⃗j∥\boldsymbol{\dfrac{\langle \vec{w}_i, \vec{w}_j \rangle}{\|\vec{w}_i\| \, \|\vec{w}_j\|}}∥wi∥∥wj∥⟨wi,wj⟩ , the cosine of the angle between them. Used to compare documents represented as vectors of word counts.Example: w⃗i=(1,0,1),w⃗j=(1,1,0)\vec{w}_i = (1, 0, 1), \vec{w}_j = (1, 1, 0)wi=(1,0,1),wj=(1,1,0) : 122=12\dfrac{1}{\sqrt2 \sqrt2} = \dfrac12221=21 .
[Abstract inner product spaces] Documents are represented as vectors of word counts, one component per word of a 40 000-word vocabulary, and compared by cosine similarity.Why does this work poorly, and what does the book do instead?
Two vectors in a 40 000-dimensional space rarely point in the same direction. Instead, compare topic vectors T(w⃗i)∈R40T(\vec{w}_i) \in \mathbb{R}^{40}T(wi)∈R40 . T:Rn→RmT : \mathbb{R}^n \to \mathbb{R}^mT:Rn→Rm is a linear transformation to a few topics (e.g. m=40m = 40m=40 ); the components of T(w⃗i)T(\vec{w}_i)T(wi) are the proportions of topics (art, science, ...) in document iii .
[Abstract inner product spaces] Word-count vectors w⃗i\vec{w}_iwi of documents are mapped to topic vectors by a linear map T(w⃗)=ATw⃗T(\vec{w}) = A_T \vec{w}T(w)=ATw .Write the inner product of two topic vectors ⟨T(w⃗i),T(w⃗j)⟩\langle T(\vec{w}_i), T(\vec{w}_j) \rangle⟨T(wi),T(wj)⟩ as a generalized dot product of the word vectors.
⟨w⃗i,w⃗j⟩M\boldsymbol{\langle \vec{w}_i, \vec{w}_j \rangle_M}⟨wi,wj⟩M with metric M=ATTATM = A_T^T A_TM=ATTAT ⟨ATw⃗i,ATw⃗j⟩=w⃗iTATTATw⃗j\langle A_T \vec{w}_i, A_T \vec{w}_j \rangle = \vec{w}_i^T A_T^T A_T \vec{w}_j⟨ATwi,ATwj⟩=wiTATTATwj .
[Abstract inner product spaces] How do you prove that a proposed operation ⟨u,v⟩\langle u, v \rangle⟨u,v⟩ is, or is not, a valid inner product?
Valid: show symmetry, linearity and positive semidefiniteness for all vectors. Invalid: find one example of vectors that violates one criterion. Example: ⟨u,v⟩=u1v1−u2v2\langle u, v \rangle = u_1 v_1 - u_2 v_2⟨u,v⟩=u1v1−u2v2 on R2\mathbb{R}^2R2 is invalid: ⟨(0,1),(0,1)⟩=−1<0\langle (0, 1), (0, 1) \rangle = -1 < 0⟨(0,1),(0,1)⟩=−1<0 .
[Gram–Schmidt orthogonalization] What are the three "quality grades" of a basis, from best to worst?
Orthonormal Mutually orthogonal vectors of length 1. Example: {(1,0),(0,1)}\{(1, 0), (0, 1)\}{(1,0),(0,1)} Orthogonal Mutually orthogonal vectors. Example: {(1,1),(1,−1)}\{(1, 1), (1, -1)\}{(1,1),(1,−1)} Generic Any nnn linearly independent vectors of an nnn -dimensional space. Example: {(1,0),(1,1)}\{(1, 0), (1, 1)\}{(1,0),(1,1)}
[Gram–Schmidt orthogonalization] What does Gram–Schmidt orthogonalization do?
It turns a basis {v1,…,vn}\{v_1, \dots, v_n\}{v1,…,vn} of an inner product space VVV into an orthonormal basis {e^1,…,e^n}\{\hat{e}_1, \dots, \hat{e}_n\}{e^1,…,e^n} of VVV , with ⟨e^i,e^j⟩=1\langle \hat{e}_i, \hat{e}_j \rangle = 1⟨e^i,e^j⟩=1 if i=ji = ji=j and 000 otherwise. It uses only the inner product, so it works for vectors of Rn\mathbb{R}^nRn , matrices, polynomials, and so on. It keeps the spans: span{e^1,…,e^j}=span{v1,…,vj}\operatorname{span}\{\hat{e}_1, \dots, \hat{e}_j\} = \…
[Gram–Schmidt orthogonalization] What is the projection Πe(u)\Pi_e(u)Πe(u) of a vector uuu onto the line spanned by a vector eee ?
Πe(u)=⟨u,e⟩∥e∥2 e\boldsymbol{\Pi_e(u) = \dfrac{\langle u, e \rangle}{\|e\|^2} \, e}Πe(u)=∥e∥2⟨u,e⟩e For a unit vector e^\hat{e}e^ : Πe^(u)=⟨u,e^⟩ e^\Pi_{\hat{e}}(u) = \langle u, \hat{e} \rangle \, \hat{e}Πe^(u)=⟨u,e^⟩e^ .Example: u=(2,3),e=(1,1)u = (2, 3), e = (1, 1)u=(2,3),e=(1,1) : Πe(u)=52(1,1)=(52,52)\Pi_e(u) = \tfrac{5}{2}(1, 1) = (\tfrac52, \tfrac52)Πe(u)=25(1,1)=(25,25) .