Zero technique in matrix

1 引言

矩阵计算不仅在线性代数中, 而且在整个数学, 乃至物理及其他学科中都有重要的地位.

刘绍学先生曾说:“1962年在颐和园龙王庙会议期间, 万哲先学兄对我说:‘搞典型群研究我们掌握一些基本手法和招数, 你们搞环论的有哪些手法和招数?’”“ (20世纪) 70年代在一次出数学竞赛题的会议中与华罗庚先生在他的房间闲谈.他对我说:‘国外把我说 (骂) 成是玩矩阵的魔鬼.……表面上你看我搞的是多复变函数、偏微分方程, 实际上骨子里还是我的矩阵技巧.’”^[1]

可见矩阵技巧是在华罗庚学派的“基本手法和招数”之一.

许以超先生说“打洞”是“矩阵计算中的最基本的技巧”.^[2]数学中最基本的技巧, 也是最重要、最有用的技巧.冯克勤先生有段很有趣的回忆:“20世纪70年代, 当我成为科大的一名教员时, 曾肯成先生对当年科大的情景说过几句格言, 我只记得其中的两句.一句是‘科大是放羊, 而不是喂猪’, 另一句是‘龙生龙, 凤生凤, 华罗庚的学生会打洞’.”^[1]

我们想在此谈谈对打洞技巧的一些认识, 以求大家的指导.

2 什么是打洞技巧

什么是打洞技巧?我们介绍许以超先生的讲法^[2].

以$I_k$表示域$\boldsymbol F$上的k阶单位矩阵.设A是域F上的m×n阶矩阵 (即A∈F^m×n) , 且

$A = (\begin{matrix} B & C \\ D & E \end{matrix})$ (2.1)

于是当B是r阶方阵, 且detB≠0时有

$(\begin{matrix} Ι_{r} & 0 \\ - D B^{- 1} & Ι_{m - r} \end{matrix}) (\begin{matrix} B & C \\ D & E \end{matrix}) = (\begin{matrix} B & C \\ 0 & E - D B^{- 1} C \end{matrix})$ , (2.2)

$(\begin{matrix} B & C \\ D & E \end{matrix}) (\begin{matrix} Ι_{r} & - B^{- 1} C \\ 0 & Ι_{n - r} \end{matrix}) = (\begin{matrix} B & 0 \\ D & E - D B^{- 1} C \end{matrix})$ . (2.3)

以上两式分别将 (2.1) 式中的D, C变成了0, 而0在电报语言中称为“洞”, 因此这种方法称为“打洞”.

类似地, 当E是k阶方阵, 且detE≠0时有

$(\begin{matrix} Ι_{m - k} & - C E^{- 1} \\ 0 & Ι_{k} \end{matrix}) (\begin{matrix} B & C \\ D & E \end{matrix}) = (\begin{matrix} B - C E^{- 1} D & 0 \\ D & E \end{matrix})$ , (2.4)

$(\begin{matrix} B & C \\ D & E \end{matrix}) (\begin{matrix} Ι_{n - k} & 0 \\ - E^{- 1} D & Ι_{k} \end{matrix}) = (\begin{matrix} B - C E^{- 1} D & C \\ 0 & E \end{matrix})$ , (2.5)

如果A是2阶方阵, 这时 (2.1) 式变为

$A = (\begin{matrix} b & c \\ d & e \end{matrix})$ . (2.1′)

如果b≠0, (2.2) 式与 (2.3) 式分别变为

$(\begin{matrix} 1 & 0 \\ - d b^{- 1} & 1 \end{matrix}) (\begin{matrix} b & c \\ d & e \end{matrix}) = (\begin{matrix} b & c \\ 0 & e - d b^{- 1} c \end{matrix})$ , (2.2′)

$(\begin{matrix} b & c \\ d & e \end{matrix}) (\begin{matrix} 1 & - b^{- 1} c \\ 0 & 1 \end{matrix}) = (\begin{matrix} d & 0 \\ d & e - d b^{- 1} c \end{matrix})$ , (2.3′)

类似地, 当e≠0时, (2.4) 式与 (2.5) 式分别变为

$(\begin{matrix} 1 & - c e^{- 1} \\ 0 & 1 \end{matrix}) (\begin{matrix} b & c \\ d & e \end{matrix}) = (\begin{matrix} b - c e^{- 1} d & 0 \\ d & e \end{matrix})$ , (2.4′)

$(\begin{matrix} b & c \\ d & e \end{matrix}) (\begin{matrix} 1 & 0 \\ - e^{- 1} d & 1 \end{matrix}) = (\begin{matrix} b - c e^{- 1} d & c \\ 0 & e \end{matrix})$ . (2.5′)

(2.2′) 式与 (2.4′) 式是将 (2.1′) 式中矩阵A进行一次初等行变换, (2.3′) 式与 (2.5′) 式是将 (2.1′) 式中矩阵A进行一次初等列变换.因此打洞技巧是矩阵一行减另一行的若干倍, 或一列减另一列的若干倍这两类初等变换的推广.由此可知, 若在 (2.1) 中, C或D可逆, 也可将B, E打成洞.

注如果我们将域F改为含幺元的交换环, 将条件detB≠0, detE≠0分别换为B, E为可逆方阵, 打洞法仍然有效.条件detB≠0, detE≠0并不等价于B, E为可逆方阵.

3 打洞技巧的应用举例

本节我们用一些例子来说明打洞技巧的应用.

3.1 用打洞技巧计算行列式

打洞技巧的应用当首推“将高阶行列式的计算化为低阶行列式的计算”^[2].

例1 设A∈F^n×n, 且$A=\left(\begin{array}{ll}B & C \\ D & E\end{array}\right), B \in {\boldsymbol F}^{r \times r},\det B\ne0$.试证

detA=detB·det (E-DB^-1C) . (3.1)

证明因为detB≠0, 故B可逆.于是 $(\begin{matrix} Ι_{r} & 0 \\ - D B^{- 1} & Ι_{n - r} \end{matrix}) (\begin{matrix} B & C \\ D & E \end{matrix}) = (\begin{matrix} B & C \\ 0 & E - D B^{- 1} C \end{matrix}) .$

而 $\det (\begin{matrix} Ι_{r} & 0 \\ - D B^{- 1} & Ι_{n - r} \end{matrix}) = 1$ .所以 (3.1) 式成立.

矩阵计算中另一个技巧是所谓 “摄动法”, 常与打洞技巧一起用.

例2 设A、B、C、D∈F^n×n, F的特征为0, 且AC=CA.试证

| \begin{matrix} A & B \\ C & D \end{matrix} | = | A D - C B |

. (3.2)

证明令$A(λ)=λI_n+A$.则$\det A(\lambda)$是$\lambda$的$n$次多项式,至多$n$个根.由$AC=CA$,有$A(λ)C=CA(λ)$.若$\det A(\lambda)≠0$,则$A(\lambda)$可逆, 且有

于是 $\det (\begin{matrix} A (λ) & B \\ C & D \end{matrix}) = \det A (λ) \det (D - C A (λ)^{- 1} B) = \det (A (λ) D - C B) .$

由于 $\det (\begin{matrix} A (λ) & B \\ C & D \end{matrix}), \det (A (λ) D - C B)$ 都是$λ$的有限次多项式,且若$\det A(λ)≠0$, 则

$\det (\begin{matrix} A (λ) & B \\ C & D \end{matrix}) = \det (A (λ) D - C B)$ , (3.3)

故 (3.3) 对任何λ成立.特别地, 对λ=0也成立, 于是结论成立.

注如果F的特征不是0, 用摄动法时要特别当心.如果F是实数域或复数域时, 在 (3.3) 中令λ→0, 则可知 (3.2) 成立.摄动法实际是源于此.

矩阵乘法的结合性导致对一个矩阵的行变换和列变换的交换性, 于是行、列变换可同时进行, 在打洞技巧中要求 (2.1) 中的B, C, D, E至少有一个可逆, 对特殊情况也不一定.

例3 设A, B∈F^n×n.试证

| \begin{matrix} A & B \\ B & A \end{matrix} | = | A + B | \cdot | A - B |

(3.4)

证明注意到$\left(\begin{array}{cc}I_{n} & I_{n} \\ 0 & I_{n}\end{array}\right)\left(\begin{array}{cc}A & B \\ B & A\end{array}\right)\left(\begin{array}{cc}I_{n} & -I_{n} \\ 0 & I_{n}\end{array}\right)=\left(\begin{array}{cc}A+B & A+B \\ B & A\end{array}\right)\left(\begin{array}{cc}I_{n} & -I_{n} \\ 0 & I_{n}\end{array}\right)=\left(\begin{array}{cc}A+B & 0 \\ B & A-B\end{array}\right)$

于是 (3.4) 成立.

3.2 用打洞技巧求逆矩阵及判断矩阵的可逆性

判断矩阵是否可逆及求可逆矩阵是线性代数中的重要问题.打洞技巧也是很有用的.

例4 设A∈F^n×n, detA≠0, B∈F^r×r, detB≠0, 且 $A = (\begin{matrix} B & C \\ D & E \end{matrix})$ , 试证

$A^{- 1} = (\begin{matrix} Ι_{r} & - B^{- 1} C \\ 0 & Ι_{n - r} \end{matrix}) (\begin{matrix} B^{- 1} & 0 \\ 0 & (E - D B^{- 1} C)^{- 1} \end{matrix}) (\begin{matrix} Ι_{r} & 0 \\ - D B^{- 1} & Ι_{n - r} \end{matrix})$ . (3.5)

证明因为detA≠0, detB≠0, 故A, B可逆.又$\left(\begin{array}{ll}B & C \\ D & E\end{array}\right)\left(\begin{array}{cc}I_{r} & -B^{-1} C \\ 0 & I_{n-r}\end{array}\right)=\left(\begin{array}{cc}B & 0 \\ D & E-D B^{-1} C\end{array}\right)$

故det (E-DB^-1C) =detA/detB≠0.因此E-DB^-1C可逆.再由

$(\begin{matrix} B & 0 \\ D & E - D B^{- 1} C \end{matrix}) (\begin{matrix} B^{- 1} & 0 \\ 0 & (E - D B^{- 1} C)^{- 1} \end{matrix}) = (\begin{matrix} Ι_{r} & 0 \\ D B^{- 1} & Ι_{n - r} \end{matrix})$ , $\left(\begin{array}{cc}I_{r} & 0 \\ D B^{-1} & I_{n-r}\end{array}\right)\left(\begin{array}{cc}I_{r} & 0 \\ -D B^{-1} & I_{n-r}\end{array}\right)=I_{n}$

得 (3.5) 成立.

例5 设A, D分别为F上m阶, n阶可逆方阵.则矩阵 $Η = (\begin{matrix} A & B \\ C & D \end{matrix})$ 为可逆矩阵当且仅当A-BD^-1C与D-CA^-1B都是可逆矩阵.

证明因为A, D可逆, 于是有$\left(\begin{array}{cc}I_{m} & 0 \\ -C A^{-1} & I_{n}\end{array}\right)\left(\begin{array}{ll}A & B \\ C & D\end{array}\right)=\left(\begin{array}{cc}A & B \\ 0 & D-C A^{-1} B\end{array}\right), \quad\left(\begin{array}{ll}A & B \\ C & D\end{array}\right)\left(\begin{array}{cc}I_{m} & 0 \\ -D^{-1} C & I_{n}\end{array}\right)=\left(\begin{array}{cc}A-B D^{-1} C & B \\ 0 & D\end{array}\right)$

因此 detH=detAdet (D-CA^-1B) =detDdet (A-BD^-1C) .

因而, H可逆, 当且仅当D-CA^-1B可逆, 当且仅当A-BD^-1C可逆.

打洞技巧与数学归纳法结合在一起使用是很常见的情形.

例6 设A= (a_ij) _n×n∈R^n×n满足条件:a_ij≤0 (i≠j) ; $A (\begin{array}{l} 1 2 \dots k \\ 1 2 \dots k \end{array}) ＞ 0 (1 \leq k \leq n)$ .则有:A^-1的所有元素非负;存在X= (x₁, …, x_n) ′, x_i>0 (1≤i≤n) 使得AX中每个元素皆正.

证明对n作归纳证明.n=1时, 命题显然成立.设n-1时命题已成立.对A作如下分块$$A=\left(\begin{array}{cc}A_{n-1} & \alpha \\ \beta & a_{nn}\end{array}\right)$$

于是有A_n-1可逆, 且A $_{n - 1}^{- 1}$ 中每个元素非负.且$\left(\begin{array}{cc}I_{n-1} & 0 \\ -\beta A_{n-1}^{-1} & 1\end{array}\right)\left(\begin{array}{cc}A_{n-1} & \alpha \\ \beta & a_{nn}\end{array}\right)=\left(\begin{array}{cc}A_{n-1} & \alpha \\ 0 & a_{nn}-\beta A_{n-1}^{-1} \alpha\end{array}\right)$

令d=a_nn-βA $_{n - 1}^{- 1}$ α.则d=detA/detA_n-1>0.又$\left(\begin{array}{cc}I_{n-1} & -\frac{1}{d} \alpha \\ 0 & 1\end{array} \right)\left(\begin{array}{cc}A_{n-1} & \alpha \\ 0 & d\end{array}\right)=\left(\begin{array}{cc}A_{n-1} & 0 \\ 0 & d\end{array}\right)$

因而有 $A^{- 1} = (\begin{matrix} A_{n - 1}^{- 1} & 0 \\ 0 & d^{- 1} \end{matrix}) (\begin{matrix} Ι_{n - 1} & - \frac{1}{d} α \\ 0 & 1 \end{matrix}) (\begin{matrix} Ι_{n - 1} & 0 \\ - β A_{n - 1}^{- 1} & 1 \end{matrix}) .$

由于A $_{n - 1}^{- 1}$ 中每个元素非负, d>0, α, β中元素非正, 于是上式右面三个矩阵中元素都非负.因而A^-1中元素非负.记A^-1= (b_ij) .于是b_ij≥0.

令 $X = \sum_{j = 1}^{n} c o l_{j} A^{- 1} = (x_{1}, \dots, x_{n})^{'}$ .则 $x_{i} = \sum_{j = 1}^{n} b_{i j}$ .由A^-1可逆, 故x_i>0, 且

$A X = \sum_{j = 1}^{n} A c o l_{j} A^{- 1} = \sum_{j = 1}^{n} c o l_{j} A A^{- 1} = (1, 1, \dots, 1)^{'}$ .

故AX中每个元素为正数.

注本例中的矩阵A及其性质在线性不等式理论和Kac-Moody代数理论中是很重要的.

3.3 打洞技巧与二次型理论

用线性代数研究二次型是将二次型化为对称矩阵.将高阶对称矩阵化为低阶对称矩阵既是基本方法也是基本任务.

例7 设A, B, C, D∈F^n×n, A可逆对称, B′=C, 证明存在可逆方阵T, 使 $Τ^{'} (\begin{matrix} A & B \\ C & D \end{matrix}) Τ$ 为准对角方阵.

证明因为A可逆对称.于是A^-1对称.注意到$\left(\begin{array}{cc}I_{n} & 0 \\ -C A^{-1} & I_{n}\end{array}\right)\left(\begin{array}{cc}A & B \\ C & D\end{array}\right)\left(\begin{array}{cc}I_{n} & -\left(A^{-1}\right)^{\prime} C^{\prime} \\ 0 & I_{n}\end{array}\right)=\left(\begin{array}{cc}A & B \\ 0 & D-C A^{-1} B\end{array}\right)\left(\begin{array}{cc}I_{n} & -\left(A^{-1}\right)^{\prime} C^{\prime} \\ 0 & I_{n}\end{array}\right)=\left(\begin{array}{cc}A & 0 \\ 0 & D-C A^{-1} B\end{array}\right)$

因此结论成立.

注在此题中, 若D也是对称的, 则整个矩阵 $(\begin{matrix} A & B \\ C & D \end{matrix})$ 是对称的.

例8 设Q为n阶实正定对称矩阵, X为n维实列向量.证明

0≤X′ (Q+XX′) ^-1X<1. (3.6)

证明设A=Q+XX′.因Q正定, XX′半正定, 故A正定, 因此A^-1也正定.因而

0≤X′ (Q+XX′) ^-1X.

再由A正定, 知detA>0, 而且有可逆矩阵P使得Q=P′P.因此

$$\left(\begin{array}{cc}P^{\prime} & X \\ 0 & 1\end{array}\right)\left(\begin{array}{cc}P & 0 \\ X^{\prime} & 1\end{array}\right)=\left(\begin{array}{cc}P^{\prime} P+X X^{\prime} & X \\ X^{\prime} & 1\end{array}\right)=\left(\begin{array}{cc}A & X \\ X^{\prime} & 1\end{array}\right)$$

又 $(\begin{matrix} Ι_{n} & 0 \\ - X^{'} A^{- 1} & 1 \end{matrix}) (\begin{matrix} A & X \\ X^{'} & 1 \end{matrix}) = (\begin{matrix} A & X \\ 0 & - X^{'} A^{- 1} X + 1 \end{matrix}) .$

于是 $(- X^{'} A^{- 1} X + 1) \det A = | \begin{matrix} A & X \\ X^{'} & 1 \end{matrix} | = (\det Ρ)^{2} ＞ 0 .$

因此 (3.6) 式成立.

3.4 打洞技巧的其他应用

下面的例子说明用打洞法可将线性方程组中未知数个数减少, 即消元.

例9 设A∈F^n×n, 且 $A = (\begin{matrix} A_{1} & A_{2} \\ A_{3} & A_{4} \end{matrix})$ .其中A₁∈F^k×k, A₄∈F^{(n-k) × (n-k)}, 且A₄可逆.又

$$X=\left(\begin{array}{l}X_{1} \\ X_{2}\end{array}\right), \quad B=\left(\begin{array}{l}B_{1} \\ B_{2}\end{array}\right)$$

其中B₁∈F^k×1, B₂∈F^{(n-k) ×1}.X₁, X₂分别为k×1, (n-k) ×1的未知矩阵.则线性方程组

AX=B (3.7)

中前k个未知数, 即X₁满足线性方程组

(A₁-A₂A $_{4}^{- 1}$ A₃) X₁=B₁-A₂A $_{4}^{- 1}$ B₂. (3.8)

证明在 (3.7) 的两边左乘 $(\begin{matrix} Ι_{k} & - A_{2} A_{4}^{- 1} \\ 0 & Ι_{n - k} \end{matrix})$ , 则由

$(\begin{matrix} Ι_{k} & - A_{2} A_{4}^{- 1} \\ 0 & Ι_{n - k} \end{matrix}) (\begin{matrix} A_{1} & A_{2} \\ A_{3} & A_{4} \end{matrix}) (\begin{matrix} X_{1} \\ X_{2} \end{matrix}) = (\begin{matrix} Ι_{k} & - A_{2} A_{4}^{- 1} \\ 0 & Ι_{n - k} \end{matrix}) (\begin{matrix} B_{1} \\ B_{2} \end{matrix})$ ,

知 $(\begin{matrix} A_{1} - A_{2} A_{4}^{- 1} A_{3} & 0 \\ A_{3} & A_{4} \end{matrix}) (\begin{matrix} X_{1} \\ X_{2} \end{matrix}) = (\begin{matrix} B_{1} - A_{2} A_{4}^{- 1} B_{2} \\ B_{2} \end{matrix}) .$

于是X₁满足 (3.8)

打洞技巧的要害是用“初等变换”将矩阵中的一些元素变为0.在具体处理过程中, 不必拘泥于将所研究的矩阵分为四块.

例10 证明Vandermonde行列式

$| \begin{matrix} 1 & 1 & 1 & \dots & 1 \\ a_{1} & a_{2} & a_{3} & \dots & a_{n} \\ a_{1}^{2} & a_{2}^{2} & a_{3}^{2} & \dots & a_{n}^{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{1}^{n - 1} & a_{2}^{n - 1} & a_{3}^{n - 1} & \dots & a_{n}^{n - 1} \end{matrix} | = \underset{i ＜ j}{Π} (a_{j} - a_{i})$ . (3.9)

证明注意到

$(\begin{matrix} 1 \\ - a_{1} & 1 \\ - a_{1} & 1 \\ ⋱ & ⋱ \\ - a_{1} & 1 \end{matrix}) (\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ a_{1} & a_{2} & a_{3} & \dots & a_{n} \\ a_{1}^{2} & a_{2}^{2} & a_{3}^{2} & \dots & a_{n}^{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ a_{1}^{n - 1} & a_{2}^{n - 1} & a_{3}^{n - 1} & \dots & a_{n}^{n - 1} \end{matrix}) =$ $\left(\begin{array}{ccccc}1 & 1 & 1 & \cdots & 1 \\ 0 & a_{2}-a_{1} & a_{3}-a_{1} & \cdots & a_{n}-a_{1} \\ 0 & a_{2}\left(a_{2}-a_{1}\right) & a_{3}\left(a_{3}-a_{1}\right) & \cdots & a_{n}\left(a_{n}-a_{1}\right) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & a_{2}^{n-2}\left(a_{2}-a_{1}\right) & a_{3}^{n-2}\left(a_{3}-a_{1}\right) & \cdots & a_{n}^{n-2}\left(a_{n}-a_{1}\right)\end{array}\right)$

再用数学归纳法,就可证明(3.9)式.

例11 设$a_1,a_2,…,a_n$互不相等,试证$$a_{n}^{n-1}-\alpha A_{1}^{-1} \beta=\prod_{i=1}^{n-1}\left(a_{n}-a_{i}\right)\tag{3.10}$$ 其中$$\alpha=\left(\begin{array}{cccc}a_{1}^{n-1} & a_{2}^{n-1} & \cdots & a_{n-1}^{n-1}\end{array}\right), \beta=\left(\begin{array}{c}1 \\ a_{n} \\ a_{n}^{2} \\ \vdots \\ a_{n}^{n-2}\end{array}\right), A_{1}=\left(\begin{array}{cccc}1 & 1 & \cdots & 1 \\ a_{1} & a_{2} & \cdots & a_{n-1} \\ a_{1}^{2} & a_{2}^{2} & \cdots & a_{n-1}^{2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1}^{n-2} & a_{2}^{n-2} & \cdots & a_{n-1}^{n-2}\end{array}\right)$$证明令$A=\left(\begin{array}{cc}A_{1} & \beta \\ \alpha & a_{n}^{n-1}\end{array}\right)$.由假设条件知$A_1$是可逆的,因此$$\left(\begin{array}{cc}I_{n-1} & 0 \\ -\alpha A_{1}^{-1} & 1\end{array}\right)\left(\begin{array}{cc}A_{1} & \beta \\ \alpha & a_{n}^{n-1}\end{array}\right)=\left(\begin{array}{cc}A_{1} & \beta \\ 0 & a_{n}^{n-1}-\alpha A_{1}^{-1} \beta\end{array}\right)$$比较等式两边的行列式知(3.10)式成立.

References

[1]张继平主编.新世纪代数学[M].北京:北京大学出版社, 2002:342, 355-356.

[2]许以超.线性代数与矩阵论[M].北京:高等教育出版社, 1992:98.

PREVIOUSCounting distinct determinants of generic matrices under permutation

NEXTGamma function