Linear Algebra in Python 2

\matrix{A}\bf{x}{=}\bf{b}可解的充要条件是向量\bf{b}可以写为矩阵\matrix{A} 列向量的一个线性组合。

下面是这节的四个知识点：

Elimination (消元)

Success

Failure

Back-Substitution

Elimination matrices

Matrix multiplication

1. Elimination

对于方程组（三个方程三个未知数）：

\begin{align*} x + 2y + z &= 2 \\ 3x + 8y + z = 12\\ 4y + z = 2 \end{align*}

若要写为\matrix{A}\bf{x}{=}\bf{b} 的形式，则有：

\begin{align*} \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} {=} \begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix} \end{align*}

下面我们对\matrix{A}进行elimination（消元）操作，先不管\bf{b} , 最终目标是将系数矩阵\matrix{A}化为三角形形式（不一定所有矩阵都可以化为三角形形式，也可能是阶梯形或者是梯形）。

\begin{align*} \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \\ \end{bmatrix} \end{align*}

其中，第一步是用第二行减去 3倍第一行，第二步是用第三行减去2倍第二行。下面的式子标出了每一步主元（pivot），这里要记住，主元不能为0。

屏幕快照 2017-09-13 20.20.58

如果消元到这一步说明消元成功（Elimination Success）。这也可以表示为\matrix{A} \rightarrow \matrix{U}，如果我们将上面的变化步骤作用于\bf{b}上，即是\bf{b} \rightarrow \bf{c} ：

\begin{align*} \begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix} \rightarrow \begin{bmatrix} 2 \\ 6 \\ 2 \end{bmatrix} \rightarrow \begin{bmatrix} 2 \\ 6 \\ -10 \end{bmatrix} \end{align*}

最后原式子变为\matrix{U}\bf{x}{=}\bf{c} ，进行回代操作（Back-Substitution）。

\begin{align*} x + 2y + z &= 2 \\ 2y - 2z = 6\\ 5z = -10 \end{align*}

可以容易解出方程组

\begin{align*} x = 2 \\ y = 1\\ z = -2 \end{align*}

如果上面的式子消元失败的话就不能得到三个主元，比如下面这个例子，我们就是这个矩阵不可逆。 （这里要提一句的时，如果出现主元为0的情况，第一种，暂时失效可以通过行交换来解决；第二种，当底下行中没有非0元素时，称消元彻底失败。）

\begin{align*} \matrix{U}= \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 0 \\ \end{bmatrix} \end{align*}

2. Back-Substitution

上面我们已经使用了Back-Substitution，这里我们使用Augment Matrix（增广矩阵）对于\matrix{A}

与\bf{b}同时进行消元操作：

屏幕快照 2017-09-13 21.07.20

再进行回代操作也会得到和上面一样的结果。

3. Elimination matrices

注意到，上面的的消元操作没有使用到矩阵，下面我们使用矩阵来描述消元步骤；

第一步，我们需要一个矩阵使下面的式子成立

\begin{align*} \begin{bmatrix} \\ \\ \\ \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} \end{align*}

经过运算，我们可以得出这个矩阵，即

\begin{align*} \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} \end{align*}

这个矩阵我们称为初等矩阵(\matrix{E}），因为它在(2, 1)位置进行了变换，我们把这个矩阵记为: \matrix{E}_{2 1}。

第二步，寻找一个矩阵使下面的式子成立，我们把这个矩阵记为: \matrix{E}_{3 2}。\begin{align*} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -2 & 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 & 0 & 5 \\ \end{bmatrix} \end{align*}

所以，

\begin{align*} \matrix{E}_{3 2}(\matrix{E}_{2 1} \matrix{A} ) {=} \matrix{U} \\ (\matrix{E}_{3 2}\matrix{E}_{2 1}) \matrix{A}{=} \matrix{U} \end{align*}

4. Inverses

上面我们将\matrix{A} \rightarrow \matrix{U}，如果我们需要进行\matrix{U} \rightarrow \matrix{A}操作，则称为逆操作。比如上面的矩阵我们对其进行左乘\matrix{E}_{3 2}\matrix{E}_{2 1} 操作，现在我们需要取消（undo）这些操作该怎么办？我们再左乘以\matrix{E}_{2 1}^{-1}\matrix{E}_{3 2}^{-1} (分别是\matrix{E}_{2 1}\matrix{E}_{3 2}的逆矩阵)

\begin{align*} \begin{bmatrix} 1 & 0 & 0\\ -3 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -2 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ 3 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix} \matrix{A} {=} \matrix{A} \end{align*} \\ (\matrix{E}_{2 1}^{-1}\matrix{E}_{3 2}^{-1})(\matrix{E}_{3 2}\matrix{E}_{2 1}) \matrix{A}{=} \matrix{A}

5. Permutation Matrix

使用矩阵交换另一个矩阵的行
\begin{align*} \begin{bmatrix} 0 & 1\\ 1 & 0\\ \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix} {=} \begin{bmatrix} c & d \\ a & b \end{bmatrix} \end{align*}
使用矩阵交换另一个矩阵的列
\begin{align*} \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} 0 & 1\\ 1 & 0\\ \end{bmatrix} {=} \begin{bmatrix} b & a \\ d & c \end{bmatrix} \end{align*}

这里有一个结论，行变换是左乘，列变换是右乘。

Elimination in Python

from numpy import array
from scipy.linalg import lu
a = array([[1., 2., 1.],[3., 8., 1.],[0., 4., 1.]])
pl, u = lu(a, permute_l=True)
print(u)
print(pl)
''' output
[[ 3.          8.          1.        ]
 [ 0.          4.          1.        ]
 [ 0.          0.          0.83333333]]
[[ 0.33333333 -0.16666667  1.        ]
 [ 1.          0.          0.        ]
 [ 0.          1.          0.        ]]
 
 '''