Lecture 1

  1. Linear equations and linear combination.
\[\begin{cases} 2x - y &= 0 \\ -x + 2y &= 3 \end{cases}\]

Coefficient matrix of this linear equations is:

\[\begin{vmatrix} 2 & -1 \\ -1 & 2 \end{vmatrix}\]

then, linear equations are $A x = b$:

\[\begin{vmatrix} 2 & -1 \\ -1 & 2 \end{vmatrix} \begin{vmatrix} x \\ y \end{vmatrix} = \begin{vmatrix} 0 \\ 3 \end{vmatrix}\]

Draw the row pictures of these two equations, we can easily find the solution: $(1, 2)$. Now come to the column picture:

\[x \begin{vmatrix} 2 \\ -1 \end{vmatrix} + y \begin{vmatrix} -1 \\ 2 \end{vmatrix} = \begin{vmatrix} 0 \\ 3 \end{vmatrix}\]

Now the question is to find somehow to combine these two vector int the right amounts to get the result vector. It’s a linear combination of columns. the value of $x$ and $y$ is the solution of the above equations: $(1, 2)$.

We can find that all linear combinations of these two column vectors will get any right-hand side at all. In other words, will fill the whole plane. When it comes to three-dimensional space, all linear combinations of vectors can fill the whole space, $A$ must be a non-singular matrix, an invertible matrix.

  1. Matrix multiplication by columns and by rows

Represent

\[\begin{vmatrix} 2 & 5 \\ 1 & 3 \end{vmatrix} \begin{vmatrix} 1 \\ 2 \end{vmatrix}\]

as

\[\begin{vmatrix} 2 & 5 \\ 1 & 3\end{vmatrix} \begin{vmatrix}1 \\ 2\end{vmatrix} = 1\begin{vmatrix}2 \\ 1\end{vmatrix} + 2 \begin{vmatrix}5 \\ 3 \end{vmatrix} = \begin{vmatrix}12 \\ 7\end{vmatrix}\]
  1. Matrix form of equations

$A x$ is a combination of columns of $A$.

Lecture 2

  1. elimination

Accept the first equation, multiply that equation by the right number, then subtract it from the second equation. The purpose is to eliminate $x$ in the second equation, deciding what the multiplier should be.

  1. two step

    • elimination: transform coefficient matrix to an upper trianglar matrix $U$ (choose proper pivot, multiplier and exchange rows if necessary).
    • back substitution.

  2. argumented matrix: 增广矩阵.

  3. Elimination is also a matrix multiplication.

\[\begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix}\]

Multiply the first row by (-3), then add it to the second row. The transform matrix is called elementary matrix (初等矩阵).

  1. Permutation: exchange rows to simplify the trouble.

Exchange rows: multiply on the left

\[\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} = \begin{bmatrix} c & d \\ a & b \end{bmatrix}\]

Exchange columns: multiply on the right

\[\begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} b & a \\ d & c \end{bmatrix}\]
  1. Inverses and reverse transform: how to transform $U$ to $A$: $E X = U$, then $X = E^{-1} U$.

Lecture 3

  1. Five ways of matrix multiplication:

    1. \[c_{ij} = \sum_{k=0}^{n}{a_{ik}b_{kj}}\]
    2. Think matrix multiplication as multiplying a matrix by a vector. The columns of $C$ (column space) are combinations of columns of $A$ ($A$ times a vector is a combination of the columns of $A$, and the numbers in $B$ decide what combination it is).
    \[\begin{bmatrix} a_{1} & a_{2} & \dots & a_{n} \end{bmatrix} B = AB\]
    1. The rows of $C$ are combinations of rows of $B$ (row space), and the numbers in $A$ decide what combination it is.
    \[A \begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \end{bmatrix} = AB\]
    1. Columns of $A$ times rows of $B$. $AB$ is the sum of column of $A$ times the rows of $B$.
    \[\begin{bmatrix} a_{1} & a_{2} & \dots & a_{n} \end{bmatrix} \begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \end{bmatrix} = AB\]
    1. Do multiplication by blocks.
    \[\begin{bmatrix} A1 & A2 \\ A3 & A4 \end{bmatrix} \begin{bmatrix} B1 & B2 \\ B3 & B4 \end{bmatrix} = AB\]

  2. Inverses

    1. A left reverse is also right inverse.

    2. Why a matrix may have no inverse ?

      Suppose $A$ times other matrix gave the identity, some column of the result matrix must be multiples (combination) of some other columns. The result can’t be the identity. Another explanation: if three’s a non-zero matrix $X$, and $AX = O$ holds, then $A$ must have no inverse.

    3. Conclusion: non-invertible matrices (singular matrices), some combinations of their columns gives the zero column.
    4. A times column $j$ of A inverse if column $j$ of the identity.

    5. Gauss-Jordan eliminate: start with the long matrix $\begin{bmatrix} A & I \end{bmatrix}$, eliminate, transform it to $\begin{bmatrix} I & E \end{bmatrix}$, then $E$ is the inverse of $A$.

      Explanation: let $E$ is the elimination matrix,

      \[E \begin{bmatrix} A & I \end{bmatrix} = \begin{bmatrix} EA & E \end{bmatrix} = \begin{bmatrix} I & E \end{bmatrix}\]

      So, $E$ is the inverse of matrix $A$.

Lecture 4

  1. $(AB)^{-1} = B^{-1}A^{-1}$. Explanation: $AB(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = AIA^{-1} = I$.
  2. Inverse and transpose: $(A^{-1})^T = (A^T)^{-1}$.
  3. Transposes and permutation: use matrix multiplication to produce permutations (置换) of matrices.
  4. Permutaion transform matrix $P$ is the identity matrix with reordered rows, $P^TP = I$.

Lecture 5

  1. The family of matrices that are unchanged by transposing, $\forall P, P^TP \text{ is a symmetric marix}$.
  2. Vector space: a bunch of vectors where all linear combinations (addition and scale of multiplication) still stay in the space.
  3. Example of vector space: three dimensional space $R^3$.
  4. Subspace: some vectors inside the given space that still make up vector space of their own. It’s a vector space inside a vector space. All subspaces have got to contain the origin, in other words containts the zero vector.
  5. Example of subspace: $R^2$ is subspace of $R^3$.

Lecture 6

  1. Union and intersection of subspaces.
    • Union of subspaces may be not a subspace.
    • Intersection of subspaces will also a subspaces. (for $u \in U$ and $v \in V$, $u+v$ will be in $U$ and $V$, so, $u+v \in U \cap V$).
  2. Column space of matrix: A subspace of all linear combinations of the columns.
  3. For equation $Ax = b$, when $b$ is a linear combinations of $A$ ($b$ is in the column space), the equation can be solved. In other words, $rank A = rank [A \ b]$.
  4. Null space: the solution of $Ax = 0$.

Lecture 7

  1. What’s the algorithm for solving $AX = 0$ ?
  2. The algorithm: elimination, elimination doesn’t change solution and null space.
  3. The rank of a $A$: the number of pivots after elimination.
  4. Pivot columns: the columns with the pivots. Other columns are called free columns (without pivots), free variables can be any value. Then we get the solution of original equation. The number of free variables indicates the dimensions of null space.
  5. Special solution: the special means give free variables special value!
  6. Reduced row echelon form（简化行阶梯形式）: do elimination upwords, transform upper trianglar matrix to form has zeros above and below the pivots. Matlab: rref (reduced row echelon form).

Lecture 8

  1. The condition for $Ax = b$ have a solution (equation is solvable): the rank of coefficient matrix must be equal to argumented matrix. In other words: $b$ must in the column space of $A$.
  2. Complete solutions: $x_{particular} + x_{nullspace}$. $x_{nullspace}$ means a subspace, and $x_{particular}$ means shift.
    • $x_{particular}$: a particular solution of $Ax=b$, find by set every free variables to zero.
    • $x_{nullspace}$: $A(x_p + x_n) = A x_p + A x_n = b + 0 = b$.
  3. The rank tells everything about the number of solutions.

Lecture 9

  1. A bunch of vectors linear independent: no combination gives the zero vector, except the zero combination.

    If a bunch of column vectors in a matrix $A$ are independent, the null space of $A$ will only have the zero vector.

  2. A bunch of vecotrs spanning a space means the space consists of all linear combination of those vectors.
  3. A bunch of vectors being a basis.
  4. Dimension: the rank of a matrix equals to the dimension of it’s column space.

Lecture 10

  1. Column space: the space of column vectors.
  2. Row space: the space of row vectors.
  3. Null sapce of column vectors.
  4. Null space of $A$ transpose (null space of row vectors).
  5. Row operations preserve the row space, but change the column space.
  6. Let $A$ is a matrix with $m$ rows and $n$ columns, $r = Rank(A)$,
  basis dimension
$C(A)$ pivot columns $r$
$N(A)$ special solutions of $A x = 0$ $n-r$
$C(A^T)$ the first $r$ rows after row reduction (not the original $A$) $r$
$N(A^T)$ special solutions of $A^T x = 0$ $m-r$

Lecture 11

  1. Matrix spaces.
  2. The basis and dimensions of matrix spaces.
  3. Intersection and sum of matrix spaces are also subspaces.
  4. Solutins of different equations: a combination of all special solutions.
  5. Rank one matrix are linke the building blocks for all matrices.

Lecture 12

  1. Graph and the matrix associated with it.
  2. Incidence matrix（关联矩阵） of a graph: dependent of some rows means loop in the subgraph.
  3. Matrix application: Kirchoff’s Law.
  4. Euler’s Formula: $nodes - edges + loops = 1$ corresponds to $dim N(A^T) = m - r$ where $A$ is the incidence matrix of the graph.

Lecture 13

  1. Rectangular matrices.
  2. Four subspaces: $C(A), N(A), C(A^T), N(A^T)$.
  3. For matrix $A$, $N(A)$ and $C(A^T)$ are perpendicular（正交、垂直）.

Lecture 14

  1. Orthogonality.

    • $x^Ty = 0$
    • $|x|^2 + |y|^2 = |x+y|^2$
  2. Length of vector: $|x|^2 = x^Tx$.
  3. Subspace $S$ is orthogonal to subspace $T$: every vector in $S$ is orthogonal to every vector in $T$, $ST = 0$.
  4. How to solve equations that can’t be solved: solve $Ax = b$, but $b$ is not in the column space of $A$, but the cloest problem (let $b$ as the cloest vector in column space of $A$, in other words, the projection of $b$ on $A$), the new equation $A^TAx=A^Tb$ can be solved.
  5. $A^TA$ is invertible exactly if the nullspace $N(A)$ noly has the zero vector, in other words, $A$ has independent columns.

Lecture 15

  1. Let the projection of vector $b$ on vector $a$ as $p = ax$, because of orthogonality, we can get

    \[a^T(b-ax) = 0\]

    simplify it,

    \[x = \frac{a^Tb}{a^Ta}\]

    then let projection matrix $P = \frac{aa^T}{a^Ta}$, then $p = Pb$.

  2. Let the projection of vector $b$ on space $A$ as $p = Ax$, because of orthogonality, we can get

    \[A^T(b-Ax) = 0\]

    simplify it,

    \[x = (A^TA)^{-1}A^Tb\]

    then let projection matrix $P = A(A^TA)^{-1}A^T$, then $p = Pb$. If $A$ is a invertible square matrix, obvirously $b$ is in the column space of $A$, the projection $p$ is the vector $b$ it self, and the projection matrix

    \[P = A(A^TA)^{-1}A^T = A(A^{-1}(A^T)^{-1})A^T = I\]
  3. The properties of projection matrix $P$:
    • $rank(P) = 1$.
    • $P^T = P$, means $P$ is symmetric.
    • $P^2 = P$.
    • All eigenvalues of $P$ are $0$ and $1$, because $P^2 = P \implies \lambda^2 = \lambda$.

  4. If $b$ is in the column space of $A$, then $p = Pb = b$. If $b$ is perpendicular to the column space of $A$, then $p = Pb = 0$. Vectors in the null space of $A$ transpose are perpendicular to the column space of $A$.

  5. Application: list squared, fitting by a line.

Lecture 16

  1. If $A$ has independent columns, then $A^TA$ is invertible.

    • Proof.
      • Suppose $A^TAx = 0$, then $x^TA^TAx = 0$, implies $(Ax)^TAx = 0$, we get $Ax = 0$.
      • Because $A$ has independent columns, $x$ must be $0$.
      • So, $A^TA$ is invertible.
    • Q.E.D

  2. Linear regression.

    Target formula:

    \[y = b + cx\]

    Solve the best approximate arguments $x = \begin{vmatrix} b & c \end{vmatrix}$ that makes $Y = Ax$ holds. According to the idea of projection, it’s easy to get

    \[Ax = A(A^TA)^{-1}A^T Y\]

    Then

    \[A^TAx = A^TA(A^TA)^{-1}A^T Y\]

    So, the solution for vector $x = \begin{vmatrix} b & c \end{vmatrix}$ is the solution of equation $A^TAx = A^TY$.

  3. Understand least squares regression from the point of projection: project the vector $Y$ onto the space of vector $X$ and vector $\begin{vmatrix} 1 & 1 & \dots & 1\end{vmatrix}$, and $x = \begin{vmatrix} b & c \end{vmatrix}$ is the projection matrix.

Lecture 17

  1. Orthogonal basis.
  2. Orthonormal（标准正交）vectors and orthonormal matrices:
\[q_i^T q_j = \begin{cases} 0 & i \neq j \\ 1 & i = j \end{cases}\]
  1. For orthonormal matrix $Q = \begin{bmatrix} q_1 & q_2 & \dots & q_n \end{bmatrix}$, we have $Q^TQ = I$ and $Q^T = Q^{-1}$.

  2. Adhemar construction: a way to construction orthonormal matrices.

    Let matrix $A = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \ 1 & -1 \end{bmatrix}$, $A$ is an orthonormal matrix. Then $\frac{1}{2} \begin{bmatrix} A & A \ A & -A \end{bmatrix}$ is also an orthonormal matrix.

  3. Graham and Schmidt calculation.

    For matrix $A = \begin{bmatrix} a_1 & a_2 & \dots & a_n \end{bmatrix}$ and corresponding orthonormal matrix $Q = \begin{bmatrix} q_1 & q_2 & \dots & q_n \end{bmatrix}$. First, orthogonalize:

    \[b_i = a_i - \sum_{j=1}^{i-1}\frac{\langle b_j, a_i \rangle}{\langle b_j, b_j \rangle} b_j\]

    Then, normalize:

    \[q_i = \frac{q_i}{|q_i|}\]
  4. Graham-Schmidt calculation and elimination: $A = QR$, where $Q$ is the orthonormal matrix, $R$ is upper trianglar matrix.

Lecture 18

  1. Three basic properties of determinant:

    • $det(I) = 1$.
    • Exchange two rows, reverse the sign of determinant.
    • For permutation matrices of $I$, determinant is $1$ or $-1$.

  2. Other useful properties of determinant:

    • \[\begin{vmatrix} a & b \\ c & d \end{vmatrix} = ad - bc\]
    • \[\begin{vmatrix} ta & tb \\ c & d \end{vmatrix} = t \begin{vmatrix} a & b \\ c & d \end{vmatrix}\]

    • The determinant is a linear function:

      \[\begin{vmatrix} a+a' & b+b' \\ c & d \end{vmatrix} = \begin{vmatrix} a & b \\ c & d \end{vmatrix} + \begin{vmatrix} a' & b' \\ c & d \end{vmatrix}\]

    • If a matrix $A$ has two equal rows, determinant of $A$ is zero.

    • Elimination doesn’t change the determinant:

      \[\begin{vmatrix} a & b \\ c-ka & d-kb \end{vmatrix} = \begin{vmatrix} a & b \\ c & d \end{vmatrix} + \begin{vmatrix} a & b \\ -ka & -kb \end{vmatrix} = \begin{vmatrix} a & b \\ c & d \end{vmatrix}\]

    • Determinant of diagonal matrix:

      \[det(A) = \prod_{i=1}^{n} d_i\]

    • $det(A) = 0$ extraly when $A$ is singular.

    • For all invertible matrix $A$,

      \[det(A^{-1}) = \frac{1}{det(A)}\]

    • $det(AB) = det(A) \dot det(B)$.

    • $det(kA) = k^{rank(A)} \dot det(A)$.

    • Transpose doesn’t change determinant:

      \[det(A^T) = det(A)\]

Lecture 19

  1. The formula for determinant.
  2. Cofactors（代数余子式）: cofactor of member $a_{i,j}$ is all the terms in the formual for determinant involves element $a_{i,j}$.
  3. Cofactors and determinant: \(det(M) = \sum_{i,j=1}^{n} a_{i,j} A{i, j}\)

Lecture 20

  1. Inverse matrix: \(A^{-1} = \frac{A^*}{\vert A \vert}\) where $A^*$ is the transpose of the cofactor matrix.
  2. Cramer’s rule: the solution of equation $Ax=b$ is $x_i = \frac{det(A_i)}{A}$.
  3. $\vert det(A) \vert$ indicates the volume of box.

Lecture 21

  1. Eigenvalues and eigenvectors.
  2. $\sum{\lambda_i} = trace(A)$.
  3. $\prod{\lambda_i} = det(A)$.
  4. For n-dimension unit vector $I_n$, eigenvalue is $1$, eigenvectors are all vectors in n-dimension space.
  5. If $B = A + kI$, then $\lambda_i^B = \lambda_i^A + k$. $A$ and $B$ have the same eigenvectors.
  6. For all symmetric matrices, their eigenvalues are real numbers.
  7. For all anti-symmetric matrices, their eigenvalues are pure imaginary values.

Lecture 22

  1. Diagonalize a matrix: if matrix $A$ has $n$ linear independent eigenvectors, then $S^{-1}AS = \Lambda$, where $S$ is the eigenvector matrix of $A$, and $\Lambda$ is the eigenvalue diagonal matrix.

  2. Application: $A^k = (S \Lambda S^{-1})^k = S \Lambda^k S^{-1}$.

    Example: the fibonacci sequence is $F_{k+2} = F_{k+1} + F_{k}$, write this equation in linear combination:

    \[u_{k+1} = A u_{k} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} u_{k}\]

    then

    \[u_k = A^k u_0 = {\begin{bmatrix} \frac{1-\sqrt{5}}{2} & \frac{1+\sqrt{5}}{2} \\ 1 & 1 \end{bmatrix}} {\begin{bmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{bmatrix}}^k {\begin{bmatrix} -\frac{1}{\sqrt{5}} & \frac{5+\sqrt{5}}{10} \\ \frac{1}{\sqrt{5}} & \frac{5-\sqrt{5}}{10} \end{bmatrix}} {\begin{bmatrix} 0 \\ 1 \end{bmatrix}}\]

  3. A formula for the $n_{th}$ Fibonacci number:

    \[f(n) = \frac{\phi^n-(-\phi)^{-n}}{5}\]

    where

    \[\phi = \frac{1+\sqrt{5}}{2}\]

Lecture 23

  1. The solution of first order, first derivate constant coefficient linear equations and the stability of coefficient matrix.

  2. Matrix exponential:

    • because $e^x = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \dots = \sum_{i = 0}^{} \frac{x^i}{i!}$, so for matrix $A = S^{-1} \Lambda S$,

      we have

      \[\begin{aligned} e^A &= 1+A+\frac{A^2}{2}+\frac{A^3}{6}+\dots \\ &= 1+S \Lambda S^{-1} + S \Lambda^2 S^{-1} + \frac{S \Lambda^3 S^{-1}}{6} + \dots \\ &= S e^{\Lambda} S^{-1} \end{aligned}\]

    • because $\frac{1}{1-x} = 1+x^2+x^3+\dots = \sum_{i=0}^{} x^i$, for matrix $A=S^{-1}\Lambda S$,

      we have

      \[\begin{aligned} \frac{1}{I-A} &= 1+A+A^2+\dots \\ &= 1+S \Lambda S^{-1} + S \Lambda^2 S^{-1} + dots \\ &= S \frac{1}{I-\Lambda} S^{-1} \end{aligned}\]

  3. Matrix exponential for some special kinds of matrices:

    1. If $A$ is a diagonal matrix,

      \[A = \begin{bmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \dots & \\ & & & \lambda_n \end{bmatrix}\]

      then

      \[e^A = \begin{bmatrix} e^{\lambda_1} & & & \\ & e^{\lambda_2} & & \\ & & e^{\lambda_3} & \\ & & & e^{\lambda_n} \end{bmatrix}\]

    2. If partitioned matrix

      \[A = \begin{bmatrix} A_1 & & & \\ & A_2 & & \\ & & \dots & \\ & & & A_n \end{bmatrix}\]

      then

      \[e^A = \begin{bmatrix} e^{A_1} & & & \\ & e^{A_2} & & \\ & & \dots & \\ & & & e^{A_n} \end{bmatrix}\]

  4. For different equation system $\frac{du}{dt} = Au$, if the solution is

    \[u (t) = e^{At} u(0) = S e^{\Lambda t} S^{-1} u(0)\]

    For example, for different equations

    \[\frac{du}{dt} = \begin{bmatrix} -1 & 2 \\ 1 & -2 \end{bmatrix}\]

    or equations

    \[\begin{cases} \frac{du_1}{dt} &= - u_1 + 2 u_2 \\ \frac{du_2}{dt} &= u_1 - 2 u_2 \end{cases}\]

    two eigenvalues of coefficient matrix $A$ are $0$ and $-3$, the eigenvector matrix $S$ is

    \[\begin{bmatrix} 2 & 1 \\ 1 & -1 \end{bmatrix}\]

    The solution of original different equations is

    \[u = \frac{1}{3} e^{0t} \begin{bmatrix} 2 \\ 1 \end{bmatrix} + \frac{1}{3} e^{-3t} \begin{bmatrix} 1 \\ -1 \end{bmatrix}\]

  5. Change one second order equations to an equivalent first order equation system.

    For example, for second order different equation $y’’ + by’ + ky = 0$, let $u = \begin{bmatrix} y’ \ y \end{bmatrix}$, then

    \[u' = \begin{bmatrix} y'' \\ y' \end{bmatrix} = \begin{bmatrix} -b & -k \\ 1 & 0 \end{bmatrix} \begin{bmatrix} y' \\ y \end{bmatrix}\]
  6. The key idea of this application of linear combination is using similar matrix $\Lambda = S^{-1}AS$ to uncouple dependent equations.

Lecture 24

  1. Markov matrix:

    1. every entry is greater than or equal to $0$ and less than or equal to $1$.
    2. All columns add to $1$. If the probability transition vectors are wrote as row vectors, all rows add to $1$.

  2. If $A$ and $B$ are all Markov matrices, then $AB$ is also a Markov matrix.

  3. The eigenvalues of markov matrix:

    1. $\lambda = 1$ is an eigenvalue.

      Proof: all columns add to 1, then $A - I$ is singular (all columns of matrix $A-I$ add to $0$).

    2. Every eigenvalue $\lambda$ of a Markov matrix satisfies $\vert \lambda \vert \le 1$.

      Proof: Suppose $\lambda$ is an eigenvalue of $A$ and $x$ is the corresponding eigenvector, then $Ax = \lambda x$. Let $k$ be such that $\vert x_j \vert \le \vert x_k \vert, \forall j, 1 \le j \le n$, then

      \[\sum_{j=1}^n A_{kj}x_j = \lambda x_k\]

      Hence

      \[\begin{aligned} \vert \lambda x_k \vert &= \vert \lambda \vert \cdot \vert x_k \vert \\ &= |\sum_{j=1}^n A_{kj}x_j| \\ &\le \sum_{j=1}^{n} A_{kj} |x_j| \\ &\le \sum_{j=1}^{n} A_{kj} |x_k| \\ &= |x_k| \end{aligned}\]

      So $\forall \lambda, \vert \lambda \vert \le 1$.

  4. The Markov chain stable state: $v_k = S \Lambda^k S^{-1} v_0$, there is only one entry of $\Lambda$ equals to $1$, all other eigenvalues $\vert \lambda_i \vert < 1$.
  5. Two functions $f(x)$ and $g(x)$ are orthonormal means $\int f(x) \cdot f(x) \,dx = 1$, $\int g(x) \cdot g(x) \,dx = 1$ and $\int f(x) \cdot g(x) \,dx = 0$.

  6. Fourier series: project a function onto infinite function spaces.

    • The basis is

      \[1, sin x, cos x, sin 2x, cos 2x, \dots\]

    • Fourier expansion:

      \[f(x) = \frac{a_0}{2} + \sum_{k=1}^\infty cos kx + \sum_{k=1}^\infty sin kx\]

      where

      \[\begin{cases} a_0 &= \frac{1}{\pi}\int_{-\pi}^{\pi}f(x) \,dx \\ a_k &= \frac{1}{\pi}\int_{-\pi}^{\pi}cos kx \,dx \\ b_k &= \frac{1}{\pi}\int_{-\pi}^{\pi}sin kx \,dx \end{cases}\]

Lecture 25

  1. Real symmetric matrix: $A = A^T$.

  2. Theorem: $\forall A$, if $A$ is a real symmetric matrix, eigenvalues of $A$ are all real.

    Proof: suppose $\lambda$ is a eigenvalue of $A$ and $x$ is the corresponding eigenvector, $Ax = \lambda x$, thus

    \[\begin{aligned} Ax = \lambda x &\implies \bar{A}\bar{x} = \bar{\lambda}\bar{x} \\ &\implies \bar{x}^T \bar{A}^T = \bar{x}^T\bar{\lambda} \\ &\implies \bar{x}^T \bar{A}^T x = \bar{x}^T \bar{\lambda} x \end{aligned}\]

    and

    \[Ax = \lambda x \implies \bar{x}^T A x = \bar{x}^T \lambda x\]

    then

    \[\bar{x}^T \lambda x = \bar{x}^T \bar{\lambda} x\]

    and $\bar{x}^T x \neq 0 (x \neq 0)$, $\lambda$ is real number, means that eigenvalues of $A$ are all real.

  3. Theorem: $\forall A$, if $A$ is a real symmetric matrix, and $p_1$, $p2$ are two eigenvectors of $A$ corresponding to two different eigenvalues, then $p_1$ and $p_2$ are orthogonal ($p_1^Tp_2 = 0$).

    Proof: $\lambda_1 p_1 = A p_1$, $\lambda_2 p_2 = A p_2$ and $\lambda_1 \neq \lambda_2$, then

    \[\lambda_1 p_1^T = (\lambda_1 p_1)^T = (A p_1)^T = p_1^T A^T = p_1^T A\]

    and

    \[\lambda_1 p_1^T p_2 = p_1^T A p_2 = p_1^T (\lambda_2 p_2) = \lambda_2 p_1^T p_2\]

    we have $\lambda_1 \neq \lambda_2$, thus \(p_1^T p_2 = 0\).

  4. Spectral theorem: $\forall A$, if $A$ is a real symmetric matrix, eigenvectors of $A$ are perpendicular (orthogonal). Spectrum is the set of eigenvectors of a matrix. \(A = Q \Lambda Q^{-1} = Q \Lambda Q^T\)
  5. For symmetric matrices, product of eigenvalues equals to product of pivots, and both equal to the determinant.
  6. Positive definite matrix(正定矩阵): all the eigenvalues and pivots are positive.

Lecture 26

  1. For complex matrix:
    • ${\vert z \vert}^2 = \bar{z}^T z = z^H z$ ($H$ means Hermite).
    • $<x, y> = x \bar{y}^T$
  2. For complex symmetric matrix: $\bar{A}^T = A$.
  3. Unitary matrix(酉矩阵): perpendicular complex matrix, $\bar{Q}^T Q = I$

  4. Fourier matrix:

    \[F_n = \begin{bmatrix}1 & 1 & 1 & \dots & 1 \\ 1 & w & w^2 & \dots & w^{n-1} \\ 1 & w^2 & w^4 & \dots & w^{2(n-1)} \\ \vdots & & & & \dots \\ 1 & w^{n-1} & w^{2(n-1)} & \dots & w^{(n-1)(n-1)} \end{bmatrix}\]

    where $w^n = 1$. $F_n$ is an unitary matrix, $F_n^{-1} = F_n^H$.

  5. FFT(Fast fourier transfer).

Lecture 27

  1. Positive definite matrix: $A$ is a symmetric matrix and $\forall x, x^T A x > 0$.
  2. Determinants of leading submatrices are all positive.
  3. If a n-dimensions functoin has minimum, it’s first derivatives matrix $\frac{d u}{d x}$ equals to zero and second derivatives matrix $\frac{d^2 u}{d x^2}$ is positive definite.
  4. Principal axis theorem: $A$ is symmetric and $A = Q \Lambda Q^T$, the eigenvalues (all positive) tell the lengths of the principal axes and the eigenvectors tell the directions of the principal axes.

Lecture 28

  1. Inverse of a symmetric positive definite matrix is also a positive definite matrix.

  2. Least squares: $Ax = Y \implies A^TAx=A^TY$, when $A^TA$ is positive definite, $x$ will get the best solutions.

    For retangular matrix $A \in R^{m \times n}, m > n$, $A^TA$ is symmetric matrix. When columns of $A$ are linear independent ($rank(A) = n$), $A^TA$ is positive definite:

    \[x^TA^TAx = (Ax)^T(Ax) = |Ax|^2 \ge 0\]

  3. Similar matrices: $A$ and $B$ are similar means for some invertible matrix $M$,

    \[B = M^{-1}AM\]

    Similar matrices have same eigenvalues.

  4. $A$ is diagonalizable: $A = S^{-1} \Lambda S$, $S$ is the eigenvector matrix of $A$.

  5. Jordan matrix: every Jordan block has one repeated eigenvalue and one eigenvector.

Lecture 29

  1. SVD: singular value decomposition. $A$ is a matrix that $A \in R^{m \times n}$, singular value decomposition means the linear transformation from an orthonormal basis in row space (V = $\begin{bmatrix} v_1 & v_2 & \dots & v_m \end{bmatrix}$) of $A$ into an orthonormal basis in column space (U = $\begin{bmatrix} u_1 & u_2 & \dots & u_n \end{bmatrix}$) of $A$. Of course, $U$ and $V$ are both invertible.

  2. We have $A v_i = \sigma_i u_i$ where $\sigma_i$ is the scalar factor, called singular value. Suppose $m > n$, $\sigma_i = 0, \forall i \textrm{ that } n < i \leq m$.

  3. We have $AV = \Sigma U$, where $\Sigma$ is a diagonal matrix. Then

    \[A = U \Sigma V^{-1} = U \Sigma V^T\]

    thus

    \[A^TA = V \Sigma^T U^T U \Sigma V^T = V \Sigma^2 V^T\]

    because $A^TA$ is a symmetric positive definite matrix, and $\lambda_i$ is it’s eigenvalues,

    \[\sigma_i = \sqrt{\lambda_i}\]

    obvirously, $V^T$ is the eigenvector matrix of $A^TA$.

  4. With the same approach we can get

    \[AA^T = U \Sigma^2 U^T\]

Lecture 30

  1. Linear transformation: every linear transformation leads to a matrix.
  2. Mapping: $x \to T(x)$ where $x$ is a vector.

  3. The two rules of linear transformation:

    • $T(v+w) = T(v) + T(w)$
    • $T(cv) = cT(v)$
  4. If the matrix $A$ is the matrix of some linear transformation $T$, then $T(x) = Ax$.

  5. Coordinates come from a basis, let $v = c_1v_1 + c_2v_2 + \dots + c_nv_n$, then the coordinate of $v$ on the basis

    \[\begin{bmatrix}v_1 & v_2 & \dots & v_n \end{bmatrix}$ is $(c_1, c_2, \dots, c_n)\]

Lecture 31

  1. Lossy compression.
  2. Change of basis matrix: $B = M^{-1}AM$.

Lecture 32

  1. What are all the matrices that have orthogonal eigenvectors?
    • Symmetric matrices.
    • Anti-symmetric matrices.
    • Orthogonal matices.
    • More generalize, $\forall A, AA^T = A^TA$
  2. All eigenvalues of projection matrices are $0$ and $1$ because $P^2 = P \implies \lambda^2 = \lambda$.

  3. If $\lambda$ is an arbitrary eigenvalue of an orthogonal matrix $Q$, then $\forall \lambda, \vert \lambda \vert = 1$.

    Proof:

    \[Qx = \lambda x \implies \Vert x \Vert = \vert \lambda \vert \Vert x \Vert\]
  4. All symmetric matrices and all orthogonal matrices can be diagonalized.

  5. $\forall A$ if $A$ is a symmetric and orthogonal matrix, then $\frac{1}{2}(A+I)$ is a projection matrix.

    Proof: because $\forall P$, if $P$ is a projection matrix, then $P^2 = P$, and $A$ is symmetric and orthogonal,

    \[A^2 = AA^T = AA^{-1} = I\]

    thus

    \[(\frac{1}{2}(A+I))^2 = \frac{1}{2}(A+I)\]

Lecture 33

  1. Left inverses and right inverses

    • Let $A$ is a matrix with $m \times n (m \ge n)$, and the rank of $A$ is $n$ (full column rank), then $A^TA$ is invertible ($rank(A^TA) = n$) and $A$ has the left inverse that $A_{left}^{-1} = (A^TA)^{-1}A^T$ and $A_{left}^{-1}A = I$. $AA_{left}^{-1} = A(A^TA)^{-1}A^T$ is the projection matrix that projects onto the column space of $A$.

    • Let $A$ is a matrix with $m \times n (m \le n)$, and the rank of $A$ is $m$ (full row rank), then $AA^T$ is invertible ($rank(AA^T) = m$) and $A$ has the right inverse that $A_{right}^{-1} = A^T(AA^T)^{-1}$ where $AA_{right}^{-1} = I$. $A_{right}^{-1}A = A^T(AA^T)^{-1}A$ is the projection matrix that projects onto the row space of $A$.

  2. Pseudo-inverses

    Let $A$ is a matrix with $m \times n$ and $rank(A) = r$ and the pseudo inverse of $A$ is $A^+$ that

    • $AA^+A = A$
    • $A^+AA^+ = A^+$
    • $AA^+$ and $A^+A$ are all symmetric matrices

    And, $A^+A$ is the row space projection matrix and $AA^+$ is the column space projection matrix.

  3. Solve the pseudo-inverse

    SVD: $A = U \Sigma V^T \implies A^+ = V \Sigma^+ U^T$ where $\Sigma^+ = Map[recip, \Sigma]$.

Lecture 34

  1. $\forall A$, if $A$ is a square matrix, $det(A^TA) = det(AA^T)$.
  2. $A^A$ is invertible if the null space of $A$ is just the zero vector ($A$ is column independent).

Other

Liear transformation

基$\alpha = (\alpha_1, \alpha_2, \dots, \alpha_n)$和基$\beta = (\beta_1, \beta_2, \dots, \beta_n)$之间的过渡矩阵$A$（线性变换在基$\alpha$下的矩阵）满足 \(\beta = \alpha A\) 同一个向量在两组这两组基下的坐标分别为$(a_1, a_2, \dots, a_n)$和$a_1’, a_2’, \dots, a_n’$，则有

\[\begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{bmatrix} = A \begin{bmatrix} a_1' \\ a_2' \\ \vdots \\ a_n' \end{bmatrix}\]

矩阵相似

复矩阵能相似到对角阵的条件：最小多项式无重根。n阶矩阵的最后一个不变因子等于A的最小多项式。最小多项式无重根则每个不变因子都无重根。