Korean, Edit

Chapter 2. Rank of a Matrix

Recommended Reading: 【Linear Algebra】 Table of Contents

1. Basis

2. Orthogonal Set

3. Image Space and Null Space

1. Basis

⑴ Definition: A linearly independent spanning set

⑵ Theorem 1. The number of elements in a basis of a vector space is unique: This number is called the dimension.

① Theorem 1-1. Let $V$ be an $n$-dimensional vector space and let $S=\lbrace \mathbf{y}_1,\cdots,\mathbf{y}_m \rbrace $ be a subset of $V$. If $n<m$, then $S$ is linearly dependent.

○ Proof

Let $\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n$ be a basis of $V$.

Since there are $n$ linear equations in $m$ unknowns, the resulting homogeneous system has nontrivial solutions, implying linear dependence.

② Theorem 1-2. Similarly to Theorem 1, if $n>m$, then $S$ is not a spanning set: That is, the number of vectors is insufficient.

⑶ Theorem 2. Existence of a basis of a vector space: If $\dim V=n$ and $A=\lbrace \mathbf{X}_1,\cdots,\mathbf{X}_n \rbrace $ is linearly independent, then $A$ is a basis of $V$.

○ Proof

Let $\mathbf{x}$ be an arbitrary basis vector of $V$.

Since $\lbrace \mathbf{X}_1,\cdots,\mathbf{X}_n \rbrace $ is both a spanning set and linearly independent, it is a basis of $V$.

⑷ Theorem 3. If $W$ is a subspace of a vector space $V$ and $\dim W=\dim V$, then $W=V$.

○ Proof

Let $\lbrace \mathbf{w}_1,\cdots,\mathbf{w}_n \rbrace $ be a basis of $W$ and $\lbrace \mathbf{v}_1,\cdots,\mathbf{v}_n \rbrace $ be a basis of $V$. Suppose there exists $\mathbf{v}$ such that $\mathbf{v}\in V$ and $\mathbf{v}\notin W$. (#)

If $x_{n+1}\neq 0$, this contradicts (#).

Therefore, $x_{n+1}=0$ must hold to satisfy (#), and consequently, $\mathbf{w}_1,\cdots,\mathbf{w}_n,\mathbf{v}$ are linearly independent.

This contradicts the statement that if $V$ is an $n$-dimensional vector space and $S=\lbrace \mathbf{y}_1,\cdots,\mathbf{y}_m \rbrace $ is a subset of $V$, then $S$ is linearly dependent whenever $n<m$. Thus, no such $\mathbf{v}$ exists, and hence $W=V$.

⑸ Theorem 4. For the hyperplane $\lbrace (x_1,x_2,\cdots,x_n)^{\mathsf{T}}\mid p_1x_1+p_2x_2+\cdots+p_nx_n=0,\ p_1\neq 0 \rbrace $, the following $n-1$ vectors can be chosen as a basis.

⑹ Theorem 5. Matrix representation of a linear transformation with respect to given bases

① $V,W$: Finite-dimensional vector spaces

② $T:V\rightarrow W$: Linear transformation

③ $B=\lbrace \mathbf{v}_1,\mathbf{v}_2,\cdots,\mathbf{v}_n \rbrace$: A basis of $V$

④ $B’=\lbrace \mathbf{w}_1,\mathbf{w}_2,\cdots,\mathbf{w}_m \rbrace $: A basis of $W$

⑤ Mathematical formulation

⑥ Matrix representation of $T$ with respect to the bases $B$ and $B’$

⑺ Application 1. Extension of a basis: Using reduced row echelon form (RREF)

Figure 1. Process of extending a basis to span $\mathbb{R}^5$ given $\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3$

2. Orthogonal Set

⑴ Orthogonality

⑵ Orthogonal set: A set in which any two distinct elements are orthogonal. An orthogonal set of nonzero vectors is linearly independent.

⑶ Orthogonal basis: An orthogonal set $S$ that is a basis of $V$

⑷ Orthonormal basis: An orthogonal basis $S$ satisfying $\left|\mathbf{x}_j\right|=1$ for every $j$

① For a matrix $U$ whose columns form an orthonormal basis, $U^{\mathsf{T}}U=I\iff U^{-1}=U^{\mathsf{T}}$.

⑸ Standard basis: Refers to $U=\mathcal{E}_n\equiv\lbrace \mathbf{e}_1,\mathbf{e}_2,\cdots,\mathbf{e}_n \rbrace $, which is one of the bases of $\mathbb{R}^n$.

⑹ Coordinate system

⑺ Orthogonal coordinate system: A coordinate system determined by the standard basis

⑻ Projection

① A transformation that projects an arbitrary vector onto a geometric object (e.g., a line or plane) spanned by an orthonormal basis

○ Python code example

y1 = np.array([1, 2, 3, 4])
y2 = np.array([8/3, 4/3, 0, -4/3])
u1 = y1 / np.linalg.norm(y1)
u2 = y2 / np.linalg.norm(y2)
U = np.column_stack((u1, u2))
UUT = np.dot(U, U.T)
v = np.array([1, 1, 2, 2])
proj_v = np.dot(UUT, v)
proj_v

② Projection and reconstruction of data in a lower-dimensional principal component space (cf. PCA)

○ Matrix $B$: Usually an orthonormal matrix $B$

○ Projection space: Project onto the lower-dimensional space defined by $B$ and then reconstruct the data.

③ Data projection for solving a least-squares problem: Given an arbitrary matrix $A$, a transformation that projects data onto the space associated with $A\mathbf{x}=\mathbf{b}$

○ Matrix $A$: An arbitrary matrix $A$

○ Projection space: The column space of $A$

④ Linear approximation of given data using $A\mathbf{x}=\mathbf{b}$ (ref)

⑼ Gram–Schmidt orthogonalization process

① Definition: A method for obtaining an orthogonal basis from an arbitrary basis

② Intuitive interpretation: When computing $\mathbf{y}k$, think of modifying the given $\mathbf{x}_k$ using $\mathbf{y}_1,\cdots,\mathbf{y}{k-1}$.

③ To obtain an orthonormal basis, first construct an orthogonal basis $\mathbf{y}_1,\cdots,\mathbf{y}_k$ and then normalize each vector.

⑽ Newton–Schulz orthogonalization

① Definition: A numerical method for transforming a matrix $A$ into the nearest orthogonal matrix

3. Image Space and Null Space

⑴ Overview

① Image space: Also called the column space

② Rank: Denoted by $\operatorname{rank}(T)$ or $\operatorname{rk}(T)$

③ Kernel or null space

④ Nullity: Denoted by $\operatorname{nullity}(T)$ or $\operatorname{nul}(T)$

⑤ Example 1. $T(x,y,z)=(3x-2z,y+z)^{\mathsf{T}}$

⑥ Example 2. $T(x,y)=(x-4y,x+2y,2x-y)^{\mathsf{T}}$

⑦ Example 3. When a linear transformation $T$ is represented by a matrix: Since the maximum number of linearly independent column vectors is $2$,

⑧ Example 4. When a linear transformation $T$ is represented by a matrix

⑵ Theorem 1. Rank theorem: The column rank and row rank of any matrix are equal.

⑶ Theorem 2. The rank of a matrix $A\in\mathbb{R}^{n\times m}$ is also the smallest integer $r$ such that $A=BC^{\mathsf{T}}$, where $B\in\mathbb{R}^{n\times r}$ and $C\in\mathbb{R}^{m\times r}$.

① Theorem 2-1. Necessary and sufficient condition for an arbitrary $n\times n$ symmetric positive semidefinite matrix to have rank $r$

⑷ Theorem 3. $\operatorname{rank}(AB)\neq\operatorname{rank}(BA)$ in general.

⑸ Theorem 4. For a positive integer $n$, if an $n\times n$ real matrix $A$ satisfies $A^{n+1}=O$, then $A^n=O$, where $O$ is the zero matrix. (ref)

○ Proof

We use proof by contradiction. Suppose an $n\times n$ real matrix $A$ satisfies $A^{n+1}=O$ but $A^n\neq O$. Then we can find $\mathbf{v}_1\in\operatorname{Im}(A^n)$ such that $\mathbf{v}_1\neq\mathbf{0}$. (Here, $\mathbf{0}$ denotes the zero vector.) Since $A\mathbf{v}_1\in\operatorname{Im}(A^{n+1})=\operatorname{Im}(O)=\lbrace \mathbf{0} \rbrace $, we have $A\mathbf{v}_1=\mathbf{0}$. Therefore, from $A^n\mathbf{v}_1=\mathbf{0}$, we can easily see that $\mathbf{v}_1\in\ker(A^n)$. Hence, $A^n\mathbf{v}_1\neq\mathbf{0}$ (because $\mathbf{v}_1\in\operatorname{Im}(A^n)$ and $A^n\neq O$), while $A^n\mathbf{v}_1=\mathbf{0}$ (because $\mathbf{v}_1\in\ker(A^n)$), which is a contradiction. Since the assumption is false, if an $n\times n$ real matrix $A$ satisfies $A^{n+1}=O$, then $A^n=O$.

⑹ Theorem 5. Rank-nullity theorem: If $T:U\rightarrow V$ is a linear transformation and $\dim U=n$, then the following relationship holds.

○ Proof

① Theorem 5-1. If a linear transformation $T$ is surjective, then $T$ is injective, and vice versa.

② Theorem 5-2. For an $m\times n$ matrix $A$ and an $n\times p$ matrix $B$, the following equality holds.

○ Proof 1

○ Proof 2. Using the rank-nullity theorem

③ Theorem 5-3. For an $m\times n$ matrix $A$, the following equality holds.

○ Proof

Suppose an element $A^{\mathsf{T}}\mathbf{x}$ of $\operatorname{Im}(A^{\mathsf{T}})$ also belongs to $\ker(A)$.

Therefore, since $\dim[\ker(A)\cap\operatorname{Im}(A^{\mathsf{T}})]=0$, the following holds.

④ Application 1. Buckingham Pi theorem: If $n$ independent variables can be expressed in terms of $m$ fundamental dimensions, the following transformation can be found (where each $\Pi_i$ is a dimensionless quantity).

⑺ Theorem 6. Frobenius’ rank inequality: For a $k\times\ell$ matrix $A$, an $\ell\times m$ matrix $B$, and an $m\times n$ matrix $C$, the following inequality holds.

○ Proof

Entered: April 25, 2020, 10:03