矩阵压缩

矩阵在计算机图形学、工程机算中占有举足轻重的地位。在数据结构中我们主要关心的是如何利用最小的存储空间来存储同样的一组数据。

特殊矩阵 指具有许多相同元素或者零元素，并且这些元素的分布具有一定规律的矩阵。常见的特殊矩阵有：对称矩阵、上（下）三角矩阵、对角矩阵等。
特殊矩阵的压缩方法 将特殊矩阵的相同元素的分布规律找出，并设法将其以更小的存储空间映射表示，实现压缩。

对称矩阵

若对于一个 $n$ 阶方阵 $A_{n\times n}$ 中任一元素 $a_{ij}$ 有： $a_{ij}=a_{ji}\quad (1\leq i,j\leq n)$ 则称 $A$ 为对称矩阵。

我们可以将其划分为三个部分：上三角区、主对角线、下三角区。
不难发现，对于对称矩阵来说，其上三角区的所有元素都是和下三角区的对应元素相等的，如果我们利用二维数组来存储对称矩阵就会浪费一半的空间，因此，我们可以根据对称矩阵的特性，利用一维数组 $B[n(n+1)/2]$ 存储。

如下图所示，根据对应关系，我们可以将 $a_{ij}\rightarrow b_k$ .

对称矩阵压缩

于是有：

$k=\begin{cases} \frac{i(i-1)}{2}+j-1,&i\geq j\\\\ \frac{j(j-1)}{2}+i-1,&i\lt j\\ \end{cases}$

注：此处是以数组按下标从 0 开始得出的推导

三角矩阵

如图所示，下三角矩阵就是指其上三角区所有元素都是零或者同一常量的矩阵，而上三角矩阵也是对应的定义。

三角矩阵示意图

对下三角矩阵压缩的存储思想也和对称矩阵类似，不同之处在于，我们存储完下三角的不同元素的内容之后，还需增设一个空间来保存上三角区的常量（如图）

下三角矩阵的压缩

所以，对于下三角矩阵，有：

$k=\begin{cases} \frac{i(i-1)}{2}+j-1,&i\geq j\\\\ \frac{n(n+1)}{2},&i\lt j\\ \end{cases}$

而对于上三角矩阵，有：

$k=\begin{cases} \frac{(i-1)(2n-i+2)}{2}+(j-i),&i\leq j\\\\ \frac{n(n+1)}{2},&i\gt j\\ \end{cases}$

其推导示意图如下：
上三角矩阵的压缩

对角矩阵

对角矩阵又称带状矩阵。是指在 $n$ 阶方阵中，非零元素集中在主对角线及其两侧。
即对任一元素 $a_{ij}$ 当 $|i-j|\gt d$ 时有 $a_{ij}=0$ . 记 $L=2d+1$ 为（奇数），则所得矩阵就是含有 $L$ 条对角线的带状区域内才有值的矩阵，称为 $L$ 对角矩阵。