前言

矩阵相信大家都不会陌生，在“线性代数”、“统计学”等课程中我们常常会和它打交道。不过，如果没有学过也别慌，这里会科普下矩阵的定义，后面的内容和那些课程也没什么关系。

矩阵是一个二维的数学结构，由若干行和若干列组成。矩阵的大小由它的行数和列数决定，通常表示为“m×n”，其中 m 是行数，n 是列数。如果 m = n，那么这个矩阵又称为方阵。
一个矩阵可以用以下形式表示

m×n矩阵

了解完矩阵的概念后，我们可以把一行看作是一个一维数组。因此，一个矩阵显然在我们编程时，用二维数组表示是非常合适的。但是，有些情况下，从节约存储空间的角度出发，这种存储是不太合适的，比如：三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。我们把这些矩阵称为特殊矩阵。这篇文章旨在和大家一起从存储的角度来考虑这些特殊矩阵的存储方法。

对称矩阵

在一个 ｎ 阶方阵中，有 a[i][j] = a[j][i]，其中 i ≥ 1，j ≤ n，这种矩阵又称为对称矩阵。如下图

4阶对称矩阵

显然，如果完整地存储整个对称矩阵是没有必要的，我们存储上三角或者下三角即可。这样，原来所需的 n × n 个存储单元就变成了 n × (n+1) ÷ 2 个存储单元了，节省了 n × (n-1) ÷ 2 个存储单元。当 n 比较大时，就可以节省比较可观的资源了。

用上面4阶的对称矩阵为例，看下三角是如何存储到数组中的，元素的位置关系是怎样的。

存储对称矩阵的数组

对于下三角，k = i × (i - 1) ÷ 2 + j - 1，k 的范围是 0 ≤ k < n(n+1)/2，其中 i ≥ j ≥ 1。

对于上三角，则有 j ≥ i ≥ 1，k = j × (j - 1) ÷ 2 + i - 1。
因此，对于 I = max(i, j)，J = min(i, j)，k = I × (I - 1) ÷ 2 + J - 1

三角矩阵

编程中的三角矩阵的定义和数学的会有点不同。下面给出百度百科的定义（数学上的定义）

数学上的三角矩阵

在编程上的三角矩阵更贴近数学上的特殊三角形矩阵，只不过主对角线以上或者以下的元素只要求是常数。
如果常熟在主对角线上方，那么这个三角矩阵又称为下三角矩阵；反之，则为上三角矩阵。

下三角矩阵

与对称矩阵相似，不过它多一个常数，所以它存储元素的个数为 n × (n+1) ÷ 2 + 1。
如果用 4 阶对称矩阵的下三角转成下三角矩阵为例子的话，存储到数组中则得到下图

存储下三角矩阵的数组

ps：常数用 c 表示，同样的 a[k] 是下三角矩阵中的任一元素。
那么 k 与 i、j 的关系如下

image.png

上三角矩阵

上三角矩阵的存储的思想和下三角矩阵的思想是相似的。这里同样以 4 阶对称矩阵的上三角转成上三角矩阵为例，存储成数组如下图（这里是以行为主序，顺序存储上三角部分，最后存储常量）

存储上三角矩阵的数组

可以得到 k 与 i、j 的关系如下

image.png

带状矩阵

带状矩阵（Banded Matrix）是指在一个二维矩阵中，除主对角线外只包含有限个非零元素，而非零元素的分布呈带状分布的一类矩阵。

带宽为3的带状矩阵

上图是一个带宽为3的带状矩阵。
计算公式如下
如果存在最小正数 m，满足当 | i - j | ≥ m 时，a[i][j] = 0，这时称 w = 2m - 1 为矩阵 A 的带宽。
因此，上图的带状矩阵是一个 w = 3(m = 2)的带状矩阵。

这里一样可以使用一维数组压缩存储，以行为主序，顺序存储非0的元素。如下图

存储带状矩阵的数组

明显，k = 2 × i + j - 3，如果满足不了这个关系的就会溢出这个数组，对应的就是 0。

稀疏矩阵

假设一个 m × n 矩阵中有 t 个非零元素，且 t 远远小于 m × n，这样的矩阵称为稀疏矩阵。
可想而知，这种矩阵如果完整地存储是很浪费存储空间的。因此，只存储非零元素的方案被提了出来。又因为稀疏矩阵的零元素是随机分布的，所以我们不能仅仅存非零元素，还要记录它们的坐标。
根据上面的结论，每一个需要存储的元素都会有三要数，行，列，值，我这里用 (i, j, v) 表示，称之为三元组。将三元组按行优先，同一行则按列号从小到大排列成一个线性表，称这个线性表为三元组表，采用顺序存储存储该表（忘了什么是顺序存储的可以看下这里传送门）。
下图为参考例子

5阶稀疏矩阵

5阶稀疏矩阵的三元组表