Matrix Multiplication

Matrix Multiplication

本文主要从不同角度思考矩阵乘法,参考 MIT 的课程 : Linear algebra

请养成这样的习惯:

  • 矩阵 = 线性变换
  • 矩阵的基本单元是行向量或者列向量, 而不是元素

多思考,很重要

1. 如何理解 \(\mathbf {y} = A \mathbf {x}\) ?

1.1 \(A \mathbf {x}\) by rows

利用 inner product 实现 : each row of \(A\) combines with \(\mathbf {x}\) to give a component of \(A\mathbf {x}\) (每次将 \(A\) 中的一行 和 列向量 \(\mathbf {x}\) 进行内积运算),也就是 : a row at a time \[
\begin {bmatrix}
1 & 1 & 6 \\
3 & 0 & 1 \\
1 & 1 & 4
\end {bmatrix}
\begin {bmatrix} 2 \\ 5 \\ 0 \end {bmatrix}
= \begin {bmatrix}
1 \cdot 2 + 1 \cdot 5 + 6 \cdot 0 \\
3 \cdot 2 + 0 \cdot 5 + 1 \cdot 0 \\
1 \cdot 2 + 1 \cdot 5 + 4 \cdot 0
\end {bmatrix}
= \begin {bmatrix} 7 \\ 6 \\ 7 \end {bmatrix}
\]

1.2 \(A\mathbf{x}\) by columns

\(\mathbf {y} = A \mathbf {x}\)\(\mathbf {y}\) 视为 \(A\) 的列向量的线性组合 (a combination of the columns of \(A\)) ,也就是说, \(\mathbf {y}\) 属于 \(A\) 的列空间 \(C(A)\) \[
\begin {bmatrix}
1 & 1 & 6 \\
3 & 0 & 1 \\
1 & 1 & 4
\end {bmatrix}
\begin {bmatrix} 2 \\ 5 \\ 0 \end {bmatrix}
= 2 \begin {bmatrix} 1 \\ 3 \\ 1\end {bmatrix} + 5 \begin {bmatrix} 1 \\ 0 \\ 1 \end {bmatrix} + 0 \begin {bmatrix} 6 \\ 1 \\ 4 \end {bmatrix}
= \begin {bmatrix} 7 \\ 6 \\ 7 \end {bmatrix}
\]
这里强烈建议养成一个习惯:

请不要将 矩阵 的基本单元看成元素,而是应该看成是 列向量组合成的行向量,或者行向量组合成的列向量

这一思想对于理解线性空间和子空间非常重要

假设 \(A\)\(m \times n\) 大小矩阵,即 \(A \in \mathbb {R}^{m \times n}\)

  • 列向量组合成的行向量 \[
    A = \begin {bmatrix}
    | & | & \cdots & | \\
    \mathbf {a}_1 & \mathbf {a}_2 &\cdots& \mathbf {a}_n \\
    | & | & \cdots & |
    \end {bmatrix}
    \]
    其中每个列向量 \(\mathbf {a}_i​\) 都满足 \(\mathbf {a}_i \in \mathbb {R}^{m \times 1}​\)

  • 行向量组合成的列向量 \[
    A = \begin {bmatrix}
    — & \mathbf {b}^T_1 & — \\
    — & \mathbf {b}^T_2 & — \\
    \vdots & \vdots & \vdots \\
    — & \mathbf {b}^T_m & —
    \end {bmatrix}
    \]
    这里加入转置符号 \(T​\) 是因为默认向量都是列向量 (column vector),如果我们想表示行向量,那么我们要加入转置符号 \(T​\)
    这里每个列向量 \(\mathbf {b}_i\) 都满足 \(\mathbf {b}_i \in \mathbb {R}^{n \times 1}\) ,因此 \(\mathbf {b}^T_i \in \mathbb {R}^{1 \times n}\)

2. 如何理解 Matrix multiplication ?

假设 \(C = AB\) ,其中 \(A \in \mathbb {R}^{m \times n}, B \in \mathbb {R}^{n \times p}\), 于是 \(C \in \mathbb {R}^{m \times p}\)

2.1 最朴素的思想: \(A\) 的每一行 和 \(B\) 的每一个列进行内积运算

Each entry in the result is that each row of \(A\) dot product with each column of \(B\)

其实这种计算方法中也包含了 列向量 和 行向量 的思想

\(A\) 视为行向量组成的列向量,\(B\) 视为 列向量组成的行向量 \[
AB = \begin {bmatrix}
— & \mathbf {a}^T_1 & — \\
— & \mathbf {a}^T_2 & — \\
\vdots & \vdots & \vdots \\
— & \mathbf {a}^T_m & —
\end {bmatrix}
\begin {bmatrix}
| & | & \cdots & | \\
\mathbf {b}_1 & \mathbf {b}_2 &\cdots& \mathbf {b}_r \\
| & | & \cdots & |
\end {bmatrix}
\]
我们简写为: \[
AB = \begin {bmatrix}
\mathbf {a}^T_1 \\
\mathbf {a}^T_2 \\
\vdots \\
\mathbf {a}^T
\end {bmatrix}
\begin {bmatrix}
\mathbf {b}_1 & \mathbf {b}_2 &\cdots& \mathbf {b}_r \\
\end {bmatrix}
\]
是不是和元素相乘很类似,我们可以直接得到: \[
AB =
\begin {bmatrix}
\mathbf {a}^T_1 \mathbf {b}_1 & \mathbf {a}^T_1 \mathbf {b}_2 & \cdots & \mathbf {a}^T_1 \mathbf {b}_r \\
\mathbf {a}^T_2 \mathbf {b}_1 & \mathbf {a}^T_2 \mathbf {b}_2 &\cdots& \mathbf {a}^T_2 \mathbf {b}_r \\
\vdots & \vdots & \ddots & \vdots \\
\mathbf {a}^T_m \mathbf {b}_1 & \mathbf {a}^T_m \mathbf {b}_2 & \cdots & \mathbf {a}^T_m \mathbf {b}_r
\end {bmatrix}
\]
其中每个元素的计算不就是 \(A\) 的每一行 和 \(B\) 的每一个列进行内积运算 吗 ?

2.2 如果把 \(A\) 视为 列向量 组成的行向量呢 ?

这里 \[
A = \begin {bmatrix}
| & | & \cdots & | \\
\mathbf {a}_1 & \mathbf {a}_2 &\cdots& \mathbf {a}_n \\
| & | & \cdots & |
\end {bmatrix} =
\begin {bmatrix}
\mathbf {a}_1 & \mathbf {a}_2 &\cdots& \mathbf {a}_n \\
\end {bmatrix}
\]
那么 \(B\) 怎么办 ? \(B\) 保持不变 \[
\begin {align}
AB &= \begin {bmatrix}
\mathbf {a}_1 & \mathbf {a}_2 &\cdots& \mathbf {a}_n \\
\end {bmatrix}
\begin {bmatrix}
b_{11} & b_{12} &\cdots & b_{1r} \\
b_{21} & b_{22} &\cdots& b_{2r} \\
\vdots & \vdots & \ddots & \vdots \\
b_{n1} & b_{n2} &\cdots & b_{nr}
\end {bmatrix} \\
&= \begin {bmatrix}
(b_{11}\mathbf {a}_1 + b_{21}\mathbf {a}_2 + \cdots + b_{n1}\mathbf {a}_n) & \cdots &
(b_{1r}\mathbf {a}_1 + b_{2r}\mathbf {a}_2 + \cdots + b_{nr}\mathbf {a}_n)
\end {bmatrix}
\end {align}
\]
可以看到: 这里 \(AB\) 的每一列都是 \(A\) 的列向量的线性组合

Every column of \(AB\) is a combination of the columns of \(A\)

2.3 如果把 \(B\) 视为 行向量 组成的列向量呢 ?

这里 \[
B = \begin {bmatrix}
— & \mathbf {b}^T_1 & — \\
— & \mathbf {b}^T_2 & — \\
\vdots & \vdots & \vdots \\
— & \mathbf {b}^T_n & —
\end {bmatrix}
= \begin {bmatrix} \mathbf {b}^T_1 \\ \mathbf {b}^T_2 \\ \vdots \\ \mathbf {b}^T_n \end {bmatrix}
\]
同样, \(A\) 保持不变 \[
\begin {align}
AB &=
\begin {bmatrix}
a_{11} & a_{12} &\cdots & a_{1n} \\
a_{21} & a_{22} &\cdots& a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m1} & a_{m2} &\cdots & a_{mn}
\end {bmatrix}
\begin {bmatrix} \mathbf {b}^T_1 \\ \mathbf {b}^T_2 \\ \vdots \\ \mathbf {b}^T_n \end {bmatrix} \\
&= \begin {bmatrix}
(a_{11} \mathbf {b}^T_1 + a_{12} \mathbf {b}^T_2 + \cdots + a_{1n} \mathbf {b}^T_n) \\ \vdots \\
(a_{m1} \mathbf {b}^T_1 + a_{m2} \mathbf {b}^T_2 + \cdots + a_{mn} \mathbf {b}^T_n)
\end {bmatrix}
\end {align}
\]
这里 \(AB\) 的每一行 都是 \(B\) 的行向量的线性组合

Each row of \(AB\) is a combination of the rows of \(B\)

这里可以引申出一个有趣的问题:

高斯行消去法 (Gaussian elimination) 可不可以从这个角度思考呢 ?

也就是说我们有一个矩阵 \(B\) ,每次对 \(B\) 进行高斯行消去运算,其实就是在 \(B\) 的左边乘以一个矩阵 \(A\) ,因为结果 \(AB\) 的每一个行就是 矩阵 \(B\) 的每一个行的线性组合啊。高斯消去法不就是这样运算的么 ?

比如我们求解如下问题: \[
A \mathbf {x} = \begin {bmatrix}
2 & 1 & 1 \\
4 & -6 & 0 \\
-2 & 7 & 2
\end {bmatrix}
\begin {bmatrix} u \\ v \\ w \end {bmatrix} =
\begin {bmatrix} 5 \\ -2 \\ 9 \end {bmatrix}
= \mathbf {b}
\]
高斯消去法步骤:

  1. \(A\) 的第二行变成它减去第一行的两倍,即 \(\mathbf {a}^T_2 = \mathbf {a}^T_2 – 2 \mathbf {a}^T_1\)
  2. \(A\) 的第三行变成它加上第一行,即 \(\mathbf {a}^T_3 = \mathbf {a}^T_3 + \mathbf {a}^T_1\)
  3. \(A\) 的第三行等于它加上第二行,即 \(\mathbf {a}^T_3 = \mathbf {a}^T_3 + \mathbf {a}^T_2\)

别忘了我们对 \(\mathbf {b}\) 也要执行相同的操作 ,于是我们得到上三角矩阵 (Upper triangular) \(U\) : \[
U \mathbf {x} = \begin {bmatrix}
2 & 1 & 1 \\
0 & -8 & -2 \\
0 & 0 & 1
\end {bmatrix}
\begin {bmatrix} u \\ v \\ w \end {bmatrix} =
\begin {bmatrix} 5 \\ -12 \\ 2 \end {bmatrix}
= \mathbf {c}
\]

那么上面的三个步骤其实是可以用矩阵表示出来的,如下所示 \[
GFE = \begin {bmatrix} 1 & & \\ & 1 & \\ & 1 & 1 \end {bmatrix}
\begin {bmatrix} 1 & & \\ & 1 & \\ 1 & & 1 \end {bmatrix}
\begin {bmatrix} 1 & & \\ -2 & 1 & \\ & & 1 \end {bmatrix}
= \begin {bmatrix} 1 & & \\ -2 & 1 & \\ -1 & 1 & 1 \end {bmatrix}
\]
\(U = GFEA\) ,这里矩阵 \(G\), \(F\), \(E\) 表示每次消去操作,利用我们前面讲的思路,这里每个矩阵可以非常快地表示出来

如果我们想从 \(U\) 变回 \(A\) ,怎么办 ?

显然, \(A = E^{-1}F^{-1}G^{-1} U\) \[
L = E^{-1}F^{-1}G^{-1} = \begin {bmatrix} 1 & & \\ 2 & 1 & \\ & & 1 \end {bmatrix}
\begin {bmatrix} 1 & & \\ & 1 & \\ -1 & & 1 \end {bmatrix}
\begin {bmatrix} 1 & & \\ & 1 & \\ & -1 & 1 \end {bmatrix}
= \begin {bmatrix} 1 & & \\ 2 & 1 & \\ -1 & -1 & 1 \end {bmatrix}
\]
这里 \(L\) 是一个 下三角矩阵 (lower triangular)

于是我们直接得到著名的 \(LU\) 分解,\(A = LU\)

\(LU\) 分解在本质上是高斯消去法的一种表达形式。将 \(A\) 通过初等行变换变成上三角矩阵 \(U\) , 那么变换矩阵 \(L\) 就是下三角矩阵

问题来了,什么情况下可以进行 \(LU\) 分解呢 ?

回到刚才的高斯消去法 3 步,其实在高斯消去法中,我们通常还会有一种操作 – 行交换 (row exchange)。

利用矩阵等于线性变换的思路 (注: 这里我之前的博客中多次提到了), 我们同样可以分析 行交换对应的矩阵 – 序列矩阵 (permutation matrix),顾名思义,就是指定行的顺序的矩阵

比如,最简单的 \(2 \times 2\) 矩阵,有两种可能的序列矩阵,即: \[
\begin {bmatrix} 1 & 0 \\ 0 & 1 \end {bmatrix} \quad \text {and} \quad
\begin {bmatrix} 0 & 1 \\ 1 & 0 \end {bmatrix}
\]
前者表示不交换行,后者表示交换行

推广到 \(n\) 阶矩阵,它的序列矩阵有 \(n!\) 种可能性

现在,如果我们可以找到一个序列矩阵使得 : \[
PA = LU
\]
这种方式也称 LU factorization with Partial Pivoting (LUP)

回答前面的问题, 方阵进行 LU 分解的条件:

Any square matrix \(A\) admits an LUP factorization. If \(A\) is invertible, then it admits an LU factorization if and only if all its leading principal minors are nonzeros. If \(A\) is a singular matrix of rank \(k\), the it admits an LU factorization if the first \(k\) leading principal minors are nonzero, although the converse is not true.

摘自 维基百科

如果对 LU 分解感兴趣,可以看下 这篇论文: https://arxiv.org/pdf/math/0506382v1.pdf

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d 博主赞过: