线性代数杂记 [linear-algebra]
线性代数杂记 [linear-algebra]
$\gdef\spaces#1{~ #1 ~}$
$\gdef\Mat{\operatorname{Mat}}$
$\gdef\Q{\mathbf{Q}}$ 令 $(M_{ij})_{1 \le i,j \le 3}$ 是包含 $9$ 个非交换独立变量的矩阵. $I_1: M \to M^{-1}$ 是对矩阵求逆, $I_2: M_{ij} \to M_{ij}^{-1}$ 是对矩阵各分量求逆, $I_3: M \to M^T$ 是矩阵的转置. 则 Kontsevich 猜测, 存在两个 $3$ 阶对角矩阵 $L,R$ 使得 $$
(I_3 \circ I_2 \circ I_1)^3(M) \spaces= LMR
$$ 且这里 $I,R$ 的分量是以 $M$ 的 $9$ 个分量 $M_{ij}$ 为变量的非交换有理函数. Kontsevich 周期性猜想 已由 Natalia Iyudu 和 Stanislav Shkarin 于 2013 年 5 月 8 日 证明, 因此这一猜想有时也被称作 Iyudu–Shkarin 定理. 不过这个证明过于暴力, 也没有对于一般的矩阵 $M \in \Mat_{n \times n}$ 回答 $n>3$ 时的 Kontsevich 周期性猜想 $$
(I_3 \circ I_2 \circ I_1)^n(M) \spaces= LMR
$$ 为何不成立 1.
如果矩阵的分量是交换元, 则 $n=1,2$ 情况很容易 验证. Iyudu 和 Shkarin 在他们的 论文 中首先验证了 Kontsevich 周期性猜想 对于 $n=2$ 非交换的情况也正确, 随后才讨论 $n=3$ 的版本. $\gdef\spaces#1{~ #1 ~}$ 设矩阵 $M$ 是 $n$ 阶对角矩阵, 即 $$
M \spaces= \begin{pmatrix}
\lambda_{1} \\
& \ddots \\
& & \lambda_{n}
\end{pmatrix}
$$ 则对非零向量 $x$ 和 $x$ 的共轭转置 $x^*$
有如下结果: $$
\min\limits_{1 \leqslant i \leqslant n}\lambda_{i}
\spaces\leqslant \frac{x^{\ast}Mx}{x^{\ast}x}
\spaces\leqslant \max\limits_{1 \leqslant i \leqslant n}\lambda_{i}
$$ 其中 $\max\limits_{1 \leqslant i \leqslant n}\lambda_{i}$ 常被称作谱半径.
Rayleigh 商定理中的对角矩阵 $M$ 可推广到 Hermite 矩阵 1, 也即 $M$ 是共轭对称的方阵 $M^* = M$, 对实数而言这当然就是对称矩阵. 稍稍回忆线性代数, 有限维谱定理说: 具体而言, 对于每个实对称矩阵 [resp., 复对称矩阵] $A$, 都存在一个实正交矩阵 [resp., 酉矩阵] 使得 $Q^* A Q$ 是对角矩阵.
广义 Rayleigh 商 $\frac{x^* A x}{x^* B x}$ 可以通过变换 $D = C^{-1} A C^*{}^{-1}$ 简化为 Rayleigh 商 $\frac{x^* D x}{(C^*x)^*(C^*x)}$, 其中 $C C^*$ 是 Hermite 正定矩阵的 Cholesky 分解. 对此, 我们也给出一例.
自伴随矩阵, 复对称矩阵. $\gdef\spaces#1{~ #1 ~}$
$\gdef\quads#1{\quad #1 \quad}$
$\gdef\eqq{\quads=}$
$\gdef\str#1{{\footnotesize #1}}$
$\gdef\sstr#1{~{\footnotesize #1}~}$
$\gdef\Mat{\operatorname{Mat}}$ 置换矩阵基本上可以认为是置换群的矩阵构造, 或者说矩阵表示. 这也可以为 此处 的结论及证明提供直观. 首先, 显然所有的置换矩阵都是单位矩阵 $I_n$ 的重新排列. 我们先从置换群 $S_2$ 也就是对换开始. 只考虑其中的非单位元 $\sigma = (1 ~~ 2)$. $$
\begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix}
\begin{pmatrix} x_1 \\ x_2 \\ \end{pmatrix}
\spaces=
\begin{pmatrix} x_2 \\ x_1 \\ \end{pmatrix}
, \quad
\begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix}
\spaces\hookrightarrow
(1 ~~ 2)
$$ 现在来考虑对换的复合, 为了通过矩阵去计算 $(2 ~~ 3)(1 ~~ 2)$, 我们实际上需要先对齐这两个方阵的阶. 换一种角度说, 对换记号 $(i ~~ j)$ 对应的并不是某个固定的方阵, 而是全体如下形式方阵当中的一个 1. $$ I_n \sstr{交换水平方向的} i ~ j \sstr{列得到的方阵} $$ 当然, 如果我们固定 $n$, 这样的对应就是唯一的了.
我们在这里强调水平方向是因为台湾等地区关于行列的称呼与大陆是相反的. 具体到矩阵乘法时, 从 $(i ~ ~ j)$ 对应的方阵中选取同阶方阵进行运算. $$
\underbrace{\begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}}_{(2 ~ 3) ~ \curvearrowright ~ I_3}
\spaces\cdot
\underbrace{\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}}_{(1 ~ 2) ~ \curvearrowright ~ I_3}
\eqq
\underbrace{\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}}_{(3 ~ 1 ~ 2) ~ \curvearrowright ~ I_3}
$$ 将矩阵乘法得到的结果翻译回置换，这当然就是 $(3 ~~ 1 ~~ 2)$, 与我们直接计算置换的复合相符. 也就是说 $$
\sigma_2\sigma_1 \quads\cong (\sigma_2 \curvearrowright I) \cdot (\sigma_1 \curvearrowright I)
$$ 规定为垂直方向当然也可行, 但这样会使得 $A\vec x$ 当中的 $A$ 必须记为它的转置 $A^T$. $\gdef\spaces#1{~ #1 ~}$
$\gdef\Mat{\operatorname{Mat}}$
$\gdef\R{\mathbf{R}}$
$\gdef\str#1{{\footnotesize #1}}$
$\gdef\sstr#1{~{\footnotesize #1}~}$
记 $\R_{\ge 0}^* = \R_{\ge 0} \cup \{\infty\}$. 从现在起, 我们对于 $\R_{\ge 0}^* ~ (= \mathcal{Q})$ 当中的许多有用的观察可以安全地转移到 $\R ~ (= R)$. 根据 半环注释, 我们优先考虑 $\Mat_{n \times n}(\mathcal{Q})$, 从最小的非平凡情况 $n=2$ 开始, 由于我们的目的是计算矩阵的逆, 故取这个半环的可逆子集也即幺半群 $\Mat_{n \times n}(\mathcal{Q})^\times$, 其中的元素会形如 $$
M \spaces= \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \quad
ad - bc \spaces\neq 0
$$ 请注意, 接下来应该考虑的是 $\square^*$. 因为我们要利用 $X^* = \frac1{1-X}$ 这个关系间接地计算 $M^{-1}$. 只要取 $X = 1-M$, 我们就得到了 $$
(1-M)^* \spaces= \frac1M \quad (= ~ M^{-1})
$$ 此处的 $1-M$ 非常微妙, 因为一般情况下它只能存在于 $\Mat_{n \times n}(R)$ 而非 $\Mat_{n \times n}(\mathcal{Q})$. 如果我们暂时忽略这个问题, 那么根据 半环注释, 由于矩阵的加法直接就是 $\mathcal{Q}$ 或者 $R$ 的加法, 而乘法来自线性空间. 此时 $M$ 与 $M^*$ 之间存在一种直接的关系, 可以说成 $(M^*)_{ij} = $ 有向图 $G$ 中所有 $i \to j$ 的路径. 具体的说, 固定下标 $i,j$, 分量 $(M^*)_{ij}$ 的值会等于以 $M$, $M^*$ 为结点, $M_{ij}$ 为箭头的 $G$ 中所有 $i \to j$ 的路径 $\hom(i,j)$ 的正则表达式. 并且从这些路径中我们也能够写出 $\hom(i,j)$ 对应的正则表达式, 这就为计算 $(M^*)_{ij}$ 提供了可能. $$\begin{aligned}
1 \longrightarrow 1 &: \quad (a+b d^*c)^* \\
1 \longrightarrow 2 &: \quad (a+b d^*c)^*b d^* \\
2 \longrightarrow 1 &: \quad d^* c(a+b d^*c)^* \\
2 \longrightarrow 2 &: \quad d^* + d^*c(a+b d^*c)^*b d^* \\
\end{aligned}$$ 简单起见记 $\alpha = (a+b d^*c)^*$, 那么上一段的讨论就是在说 $$
M^* \spaces= \begin{pmatrix}
\alpha & \alpha b d^* \\
d^* c \alpha & \quad d^* + d^*c \alpha b d^* \tag{1.1}
\end{pmatrix}
$$ 这里有两个不应忽视的问题. 其一, 虽然我们考虑的是 $\Mat_{n \times n}(\mathcal{Q})$ 上的 Kleene 星运算 $\square^*$, 但右侧的表达式中涉及了 $\mathcal{Q} ~ (= \R_{\ge 0}^*)$ 上的 Kleene 星运算 $\square^*$, 根据之前的内容, 我们可以自然地确定它就是 $a \mapsto \frac1{1-a}$. 这允许我们从 $M$ 的各个分量 $M_{ij}$ 计算出 $M^*$. 更加重要的是, 由于 $\Mat_{n \times n}(\mathcal{Q})$ 也能通过这样的方式构成闭半环, 这实际上允许我们将 $(1.1)$ 的适用范围拓展到任意大小的方阵 $\Mat_{n \times n}(\mathcal{Q})$, 此时的 $a,b,c,d$ 能够选取为 $M$ 的分块矩阵. 其二, $d^* + d^*c \alpha b d^*$ 在一般的星半环中不能直接替换为 $(d+ca^*b)^*$, 可替换的前提被称为 Conway 条件.
Conjecture. Kontsevich 周期性猜想 [kontsevich-periodicity]
Theorem. Rayleigh 商定理 [rayleigh-quotient]
Exegesis. 置换矩阵构造 [permutation-matrix]
Exegesis. 自动机与矩阵求逆 [automata-matrix]
