Computer Graphics Optimization
コンピュータグラフィックス最適化
Mathematics Refresher
Edgar SIMO-SERRA
シモセラ エドガー
Lesson Overview
- Systems of Linear Equations
- Determinant
- Adjugate
- Matrix Inversion
- Eigendecomposition
- Definiteness
- Taylor Series
Textbook
- Robert A. Beezer, A First Course in Linear Algebra, Congruent Press, 2016. ISBN: 978-0984417551.
Notation
R: real numbers (実数)R+: set of non-negative real numbers (非負実数)R++: set of positive real numbersa (正実数)Rn:n-dimensional vector (n次元ベクトル)Rm×n:m×n-dimensional matrix (m×n次元行列)(a,b,c)=[abc]=[abc]⊺x_i:i-th component of a vector, element of a set, or sequence of vectorsf\colon \mathbb{R}^p \rightarrow \mathbb{R}^q:\mathbb{R}^q-valued function on some subset of\mathbb{R}^p
Systems of Linear Equations
Definition. A System of Linear Equations (線型方程式系) is a collection of m equations based on variables x_1, x_2, \ldots, x_n in the form of:
a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 \\ \vdots \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = b_m
where the values of a_{ij}, b_i, and x_j, 1 \leq i \leq m, 1 \leq j \leq n, are from the set of complex numbers, \mathbb{C}.
Solutions of a System of Equations
Definition. A solution of a system of linear equations (線型方程式系の解) with n variables, x_1, x_2, \ldots, x_n, is an ordered list of n complex numbers, s_1, s_2, \ldots, s_n such that if we substitute s_1 for x_1, s_2 for x_2, \ldots, s_n forx_n, then for every equation of the system the left side will equal the right side, i.e., each equation is true simultaneously.
Definition. The solution set of a linear system of equations (線型方程式系の解集合) is the set which contains every solution to the system, and nothing more.
Example
Given the system of equations with n=4 variables and m=3 equations
\begin{align} x_1 + x_2 + x_3 + x_4 &= 0 \\ x_2 + x_3 + x_4 &= 0 \\ x_3 + x_4 &= 0 \end{align}
will have x_1=0, x_2=0, x_3=0 as the solution set (n-m=1 degree of freedom).
Determinant
Definition. Suppose A is a square matrix. Then its determinant (行列式), \det{(A)} = |A|, is an element of \mathbb{C} defined recursively by:
- If
Ais a1 \times 1matrix, then\det{(A)} = A_{11}. - If
Ais a matrix of sizen \times nwithn \geq 2, then
\begin{align} \det{(A)} &= A_{11} \det{(A[1|1])} − A_{12} \det{(A[1|2])} + A_{13} \det{(A[1|3])} \\ &− A_{14} \det{(A[1|4])} + \cdots + (−1)^{n+1} A_{1n} \det{(A[1|n])} \end{align}
where A[i|j] is the matrix A with the i-th row and j-th column removed.
Common Cases
For the 2 \times 2 case the determinant becomes
A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}, \quad \det{(A)} = ad-bc
For the 3 \times 3 case the determinant becomes
A = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix} \\ \det{(A)} = a\;\det{\begin{bmatrix}e&f\\h&i\end{bmatrix}} - b\;\det{\begin{bmatrix}d&f\\g&i\end{bmatrix}} + c\;\det{\begin{bmatrix}d&e\\g&h\end{bmatrix}}
Adjugate
Definiton. The cofactor matrix (余因子行列) of an n \times n matrix A is the matrix C in which each element is defined by the cofactor,
C_{ij} = \left( (-1)^{i+j} \det{(A[i|j])} \right)_{1 \leq i, j \leq n}
Definition. The adjugate (随伴行列) of A is the transpose of the cofactor matrix C of A,
\adj{(A)} = C^\intercal, \quad \adj{(A)}_{ij} = \left( (-1)^{i+j} \det{(A[j|i])} \right)_{1 \leq i, j \leq n}
Common Cases
For the 2 \times 2 case the determinant becomes
A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}, \quad \adj{(A)} = \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}
For the 3 \times 3 case the determinant becomes
A = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix} \\ \adj{(A)} = \begin{bmatrix} +\begin{bmatrix} e & f \\ h & i \end{bmatrix} & -\begin{bmatrix} b & c \\ h & i \end{bmatrix} & +\begin{bmatrix} b & c \\ e & f \end{bmatrix} \\ -\begin{bmatrix} d & f \\ g & i \end{bmatrix} & +\begin{bmatrix} a & c \\ g & i \end{bmatrix} & -\begin{bmatrix} a & c \\ d & f \end{bmatrix} \\ +\begin{bmatrix} d & e \\ g & h \end{bmatrix} & -\begin{bmatrix} a & b \\ g & h \end{bmatrix} & +\begin{bmatrix} a & b \\ d & e \end{bmatrix} \\ \end{bmatrix}
Matrix Inversion
Definition. Suppose A and B are square matrices of size n \times n such that AB=\mathbb{I}_n and BA = \mathbb{I}_n.
Then A is invertible and B is the inverse (逆行列) of A. In this situation, we write B = A^{−1}.
For a 2 \times 2 matrix, the inverse can be computed as follows:
A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}, \quad A^{-1} = \frac{1}{\det{(A)}} \adj{(A)} = \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}
A matrix will only have an inverse when it is full rank, i.e., the determinant is non-zero (ad-bc \neq 0 in the 2 \times 2 case).
Solving Linear Systems
For linear systems with a single solution, i.e., n=m, it is possible to solve them efficiently using matrix inversion. In particular, we must rewrite the linear system to the form Ax=b, and then we can solve it directly by computing x=A^{-1}b. Note that this will only work when A is full rank.
Example
Given the linear system of equations
\begin{align} x_1 + x_2 + x_3 + x_4 &= 0 \\ x_2 + x_3 + x_4 &= 0 \\ x_3 + x_4 &= 0 \\ x_4 &= 0 \end{align}
we can rewrite them as
\begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}
with solution x = A^{-1}b = (0, 0, 0, 0).
Eigendecomposition
Definition. Suppose that A is a matrix of size n \times n, x \neq 0 is a vector in \mathbb{C}^n, and \lambda is a scalar in \mathbb{C}. Then we say x is an eigenvector (固有ベクトル) of A with eigenvalue (固有値) \lambda if
Ax = \lambda x \quad .
Computation can be done as following:
Ax = \lambda x \iff Ax - \lambda \mathbb{I}_n x = 0 \iff (A - \lambda \mathbb{I}_n)x = 0
By finding values of \lambda for which (A - \lambda \mathbb{I}_n) is
singular (i.e., determinant is 0), we can obtain the eigenvalues.
Example
Given
A = \begin{bmatrix} -5 & 8 \\ -4 & 7 \end{bmatrix}
we compute as the values of \lambda that make the following equation 0
\det{(A - \lambda \mathbb{I}_n)} = \det{\left(\begin{bmatrix} -5 & 8 \\ -4 & 7 \end{bmatrix} - \begin{bmatrix} \lambda & 0 \\ 0 & \lambda \end{bmatrix}\right)} = \\ \det{\left(\begin{bmatrix} -5-\lambda & 8 \\ -4 & 7-\lambda \end{bmatrix}\right)} = \lambda^2 - 2\lambda - 3 = 0\\
Solving for \lambda we obtain that \lambda_1 = 3, and \lambda_2 = -1 as the two solutions which correspond to the two eigenvalues of A.
Definiteness
Definition. An n \times n real matrix M is said to be definite positive (正定値) if
x^\intercal M x > 0,\quad \forall x \in \mathbb{R}^n \setminus 0
Definition. An n \times n real matrix M is said to be semi-definite positive (半正定値) if
x^\intercal M x \geq 0,\quad \forall x \in \mathbb{R}^n
Definition. An n \times n real matrix M is said to be definite negative (負定値) if
x^\intercal M x < 0,\quad \forall x \in \mathbb{R}^n \setminus 0
Definition. An n \times n real matrix M is said to be semi-definite negative (非負定値) if
x^\intercal M x \leq 0,\quad \forall x \in \mathbb{R}^n
Relationship with Eigenvalues
For n \times n symmetric matrices, it is possible to use the eigenvalues \lambda_1, \ldots, \lambda_n to check the definiteness of a matrix. In particular,
\lambda_i > 0, \forall i\in[1,\ldots,n] \implies \text{definite positive}\lambda_i \geq 0, \forall i\in[1,\ldots,n] \implies \text{semi-definite positive}\lambda_i < 0, \forall i\in[1,\ldots,n] \implies \text{definite negative}\lambda_i \leq 0, \forall i\in[1,\ldots,n] \implies \text{semi-definite negative}
This is very useful to check whether or not the Hessian matrix is semi-definite positive or not as we will see in the course.
Taylor Series
Definition. The Taylor series (テイラー展開) of a function f(x) \colon \mathbb{C}^n \mapsto \mathbb{C} that is infinitely differentiable at x=a is the power series
f(a)+\frac {f'(a)}{1!} (x-a)+ \frac{f''(a)}{2!} (x-a)^2+\frac{f'''(a)}{3!}(x-a)^3+ \cdots,
where n! denotes the factorial of n.
