Overview §

Columbia University, Fall 2022 – M. Miller Eismeier – Syllabus – Course notes

Course description

The Honors Math sequence covers linear algebra and multivariable calculus with a rigorous, proofbased approach. In addition to the course content itself, the Honors sequence hopes to develop your skills as proofwriters who can clearly communicate the idea of why things are true, in addition to the usual computational content of introductory classes in calculus and linear algebra.

Honors Math A is a course in proof-based linear algebra. We will first discuss mathematical logic, then the idea of sets and functions, before moving on to linear algebra from both abstract and concrete perspectives. No calculus is used except as a source of examples.

Main definitions and theorems §

Vector spaces and subspaces §

• (Lemma 38) Basis extension lemma. If $S=\{v_1,\cdots ,v_n\}$ is any linearly independent set for a finite-dimensional vector space $V$, there is a larger set $S^{\prime }=\{v_1,\cdots ,v_n,w_1,\cdots ,w_m\}$ which is a basis for $V$ (with $k=0$ if $\text{span}(S)=V$).
• (Midterm, Problem 6) If two subspaces $U,W\subset V$ are complementary (i.e., $U,W$ intersect trivially so that $U\cap W=\{\vec{0}\}$, then $\text{dim}V=\text{dim}U+\text{dim}W=\text{dim}(U+W)$.
  • (Sample Final 1, Problem 2) For all $v\in V$, there exist unique $u\in U$ and $w\in W$ so that $v=u+w$.

Linear maps §

• (Theorem 45) Linear maps are determined by their values on a basis. Given a basis for a vector space $\{v_1,\cdots ,v_n\}\subset V$ and a list of vectors $(w_1,\cdots ,w_n)\subset W$, there exists a unique linear map $A:V\to W$ for which $A{v}_i=w_i$ for all $1\le i\le n$.
• (Theorem 49) Rank-nullity. If $A:V\to W$ is a linear map between finite-dimensional vector spaces, we have: $\text{rank}(A)+\text{null}(A)=\text{dim}(V).$
• (Corollary 50) Following the rank-nullity theorem, we have:
  • $A\text{ is injective}⟹\text{dim}(V)\le \text{dim}(W)$
  • $A\text{ is surjective}⟹\text{dim}(V)\ge \text{dim}(W)$
  • $A\text{ is bijective}⟹\text{dim}(V)=\text{dim}(W)$
• (Proposition 53) Given a linear map $A:V\to W$:
  • If $A$ is right invertible, then $A$ is surjective
  • If $A$ is left invertible, then $A$ is injective.
  • If $A$ is invertible, then $A$ is bijective.
• (Corollary 57) Invertible map theorem. If $A:V\to W$ is a linear map between two vector spaces of the same dimension, then $A\text{ is invertible}⟺A\text{ is injective, so }\text{ker}(A)=0⟺A\text{ is surjective.}$

Gauss-Jordan algorithm §

• (Proposition 70) If $M$ is an $m\times n$ matrix and $b\in {\mathbb{F}}^m$ is a vector (i.e., an $m\times 1$ matrix), and $M^{\prime }$ and $b^{\prime }$ are obtained by performing the same elementary row operation, then $A_{M}x=b⟺A_{M^{\prime }}x=b^{\prime }.$
• (HW6, Problem 4) A $n\times n$ matrix $M$ is invertible $⟺\text{rref}(M)=I_n$, the identity matrix.
• (HW6, Problem 5) Algorithm to compute the inverse of a matrix. Let $M$ be an $n\times n$ matrix. Perform the Gauss-Jordan algorithm on the pair $(M\mid I_n)$ until $(\text{rref}(M)\mid N)$ is reached for some matrix $N$. Then $M$ is invertible if and only if $\text{rref}(M)=I_n$, in which case the inverse $M^{-1}=N$.
  • Following Proposition 70, If a pair $(M\mid b)$ has solution $x$, then $(M^{\prime }\mid b^{\prime })$ has the same solution $x$.
  • If $M$ invertible, GJA transforms the system $(M\mid e_j)$ into $(\text{rref}(M)\mid v_j)=(I_n\mid v_j)$, so $v_j$ is some unique vector with $M{v}_j=e_j$.
  • The vector $v_j$ is thus the $j$‘th column of $N$.

Matrices with respect to a basis §

• (Proposition 74) The transition maps satisfy the following properties:
  • For any basis $\beta$ of $V$, we have ${\varphi }_{\beta \to \beta }=I$ is the identity map ${\mathbb{F}}^n\to {\mathbb{F}}^n$.
  • For any two bases $\beta ,{\beta }^{\prime }$ of $V$, we have ${\varphi }_{\beta \to {\beta }^{\prime }}^{-1}={\varphi }_{{\beta }^{\prime }\to \beta }$.
  • For any three bases $\beta ,{\beta }^{\prime },{\beta }^{\prime \prime }$, we have ${\varphi }_{{\beta }^{\prime }\to {\beta }^{\prime \prime }}{\varphi }_{\beta \to {\beta }^{\prime }}={\varphi }_{{\beta }^{\prime }\to {\beta }^{\prime \prime }}$.
• (Proposition 75) Let $A:V\to W$ be a linear map, and choose bases ${\beta }_V,{\beta }_V^{\prime }$ for $V$ and ${\beta }_W,{\beta }_W^{\prime }$ for $W$. Then the matrix representation of $A$ with respect to two bases is given by

Determinants §

• (Theorem 80) The determinant is well-behaved under matrix multiplication. If $M$ and $N$ are $n\times n$ matrices, then $\text{det}(MN)=\text{det}(M)\text{det}(N)$.
  • If $M$ is invertible, $\text{det}(M)\ne 0$ and $\text{det}(M^{-1})=\text{det}(M{)}^{-1}$.
• (Theorem 85) Determinant changes with elementary row or column operations.
  • If $M^{\prime }$ is obtained by swapping two rows or two columns of $M$, then $\text{det}(M^{\prime })=-\text{det}(M)$.
  • If $M^{\prime }$ is obtained by scaling a row or column of $M$ by $c$, then $\text{det}(M^{\prime })=c\text{det}(M)$.
  • If $M^{\prime }$ is obtained by adding a multiple of one row or column of $M$ to another, then $\text{det}(M^{\prime })=\text{det}(M)$.

Eigen(things) §

• (Lemma 94) If ${\lambda }_1,\cdots ,{\lambda }_k$ are the eigenvalues of $A:V\to V$, then the subspaces $E_{{\lambda }_1},\cdots ,E_{{\lambda }_k}$ are independent, so we have $E_{{\lambda }_i}\cap (E_{{\lambda }_1}+\cdots +E_{{\lambda }_{i-1}})=\{\vec{0}\}$ for all $1\le i\le k$.
• (Lemma 95) If $W_1,\cdots ,W_k\subset V$ are independent subspaces, then $\text{dim}(W_1+\cdots +W_k)=\text{dim}(W_1)+\cdots +\text{dim}(W_k)$. Furthermore, the separate bases for $W_1,\cdots ,W_k$ can be combined to form a basis for $W_1+\cdots +W_k$.
• (Theorem 97) A linear map $A:V\to V$ is diagonalizable if and only if its characteristic polynomial $p_A(\lambda )$ can be split into linear factors, and $\text{dim}{E}_{{\lambda }_i}=$ the algebraic multiplicity of ${\lambda }_i$ for every eigenvalue ${\lambda }_i$.
• (Corollary 98) If $A:V\to V$ is a linear map with $n=\text{dim}V$ distinct eigenvalues ${\lambda }_1,\cdots ,{\lambda }_n\in \mathbb{F}$, then $A$ is diagonalizable.
• (Corollary 100) If $A:V\to V$ is a linear map for some vector space $V$ over the algebraically closed field $\mathbb{F}$, then $A$ has an eigenvector; that is, there exists some $v\ne \vec{0}$ and $\lambda \in \mathbb{F}$ so that $Av=\lambda v$.

Inner product spaces §

• (Definition 54) If $V$ is an inner product space, the norm, or magnitude, is a function $||\cdot ||:V\to [0,\infty )$ defined by $\sqrt{⟨v,v⟩}\in [0,\infty )$.
• (Lemma 102) The norm on an inner product space satisfies the following properties:
  • (N1) $\Vert v\Vert \ge 0$, and $\Vert v\Vert =0⟺v=\vec{0}$.
  • (N2) $\Vert cv\Vert =|c|\Vert v\Vert$
  • (N3) $\Vert v+w{\Vert }^2=\Vert v{\Vert }^2+\Vert w{\Vert }^2+2\text{Re}⟨v,w⟩$
    • In particular, $\Vert v+w{\Vert }^2=\Vert v{\Vert }^2+\Vert w{\Vert }^2⟺⟨v,w⟩$ has no real part.

Orthogonality and orthonormal bases §

• (Definition 57) An orthonormal list of vectors in a finite-dimensional inner product space $V$ is a list of vectors $(v_1,\cdots ,v_k)$ for which $\Vert v_i{\Vert }^2=1$ and $v_1\cdot v_j=0$ for all $i\ne j$.
• (Lemma 106) If $(v_1,\cdots ,v_k)$ is an orthonormal list, it is linearly independent.
• (Proposition 107) Orthonormal basis extension. If $V$ is a finite-dimensional inner product space, every list of orthonormal vectors in $(v_1,\cdots ,v_k)\subset V$ can be extended to an orthonormal basis for $V$.

Transpose and dot product §

• (Proposition 113) If $A:{\mathbb{F}}^n\to {\mathbb{F}}^m$ is a linear map, we have $\text{ker}(A^{\ast })=\text{im}(A{)}^{\perp }$ and $\text{im}(A^{\ast })=\text{ker}(A{)}^{\perp }$.

Maps between inner product spaces §

• (Definition 59) If $V$ is an inner product space, an isometry is an invertible linear map $A:V\to V$ with $⟨A{v}_1,A{v}_2⟩=⟨v_1,v_2⟩$ for all $v_1,v_2\in V$.
  • If $V={\mathbb{R}}^n$ is a real inner product space, $A$ is called an orthogonal transformation and has a corresponding $n\times n$ orthogonal matrix. The set of orthogonal matrices is denoted $O(n)$.
  • If $V={\mathbb{C}}^n$ is complex, $A$ is called an unitary transformation and has a corresponding $n\times n$ unitary matrix. The set of unitary matrices is denoted $U(n)$.
• (Proposition 115) If $A:V\to V$ is a linear map of a finite-dimensional inner product space, then the following are equivalent:
  • $A$ is an isometry.
  • $A$ preserves norms; for all $v\in V$, we have $\Vert Av\Vert =\Vert v\Vert$.
  • $A$ satisfies the equation $A^{\ast }A=I$.
  • If $V={\mathbb{F}}^n$ and $A$ corresponds with an $n\times n$ matrix, then the columns of $A$ form an orthonormal basis for ${\mathbb{F}}^n$.
• (Lemma 118) Inner product and symmetric/Hermitian matrices.
  • A real matrix is symmetric and a complex matrix is Hermitian if and only if for all $v,w\in V$, we have $⟨Mv,w⟩=⟨v,Mw⟩$.
  • A real matrix is skew-symmetric and a complex matrix is skew-Hermitian if and only if for all $v,w\in V$, we have $⟨Mv,w⟩=-⟨v,Mw⟩$.
• (Proposition 119) The eigenvalues of a symmetric or Hermitian matrix are all real, so that its characteristic polynomial splits into linear factors over $\mathbb{R}$. The eigenvalues of a skew- matrix are all imaginary.