1. 对称矩阵#

若 $n$ 阶矩阵 $A$ 中任意元素 $a_{ij}$ 均满足 $a_{ij} = a_{j,i}$($1 \leqslant i, j \leqslant n$)，则称其为对称矩阵。其元素可分为三部分：上三角区、主对角线和下三角区。

由于上三角区与下三角区完全对称，若仍用二维数组存储，将近一半空间被浪费。为此可将n阶对称矩阵A压缩存储于一维数组 $B[n(n+1)/2]$ 中，通常仅存放下三角部分(含主对角线)。

对于元素 $a_{ij}$ ( $i \geqslant j$)，其在数组 B 中的位置由其前方的元素个数决定

第1行：1个元素 $(a_{1,1})$。

第2行：2个元素 $(a_{2,1},a_{2,2})$。

…

第 i-1 行：i-1 个元素 $(a_{i-1,1}, a_{i-1,2}, \cdots, a_{i-1,i-1})$。

第i行：j-1个元素 $(a_{i,1}, a_{i,2}, \cdots, a_{i,j-1})$。

因此，元素 $a_{i,i}$ 在数组 B 中的下标 $k=1+2+\cdots+(i-1)+j-1=i(i-1)/2+j-1$(数组下标从0开始)。元素下标之间的对应关系如下：

若数组下标从1开始，则可采用类似的推导方法，请读者自行思考。

NOTE

二维数组 A[n][n] 与 A[0...n-1][0...n-1] 写法等价，表示下标从 0 开始。若写作 A[1...n][1...n]，则表示下标从 1 开始。矩阵元素通常记为 $a_{ij}$，其行号 i 和列号 j 通常从 1 开始。

2. 三角矩阵#

在下三角矩阵中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵的类似，但是需要额外存储该常量一次。因此，可以将 n 阶下三角矩阵 A 压缩存储在 B[n(n+1)/2+1] 中。

对于元素 $a_{i,j}$($i \geq j$)，其在数组 B 中的下标为

在上三角矩阵中，下三角区所有元素均为同一常量。只需存储主对角线、上三角区上元素及该常量一次，同样将其压缩存储在 B $[n(n+1)/2+1]$ 中。

对于元素 $a_{ij}$ ( $i \leq j$)，其在数组 B 中前方的元素个数为

第1行：n个元素

第2行：n-1个元素

…

第i-1行：n-i+2个元素

第i行：j-i个元素

故元素 $a_{ij}$ 在数组 B 中的下标 $k = n + (n-1) + \cdots + (n-i+2) + (j-i+1) - 1 = (i-1)(2n-i+2)/2 + (j-i)$。元素下标之间的对应关系如下：

以上推导均假设数组下标从0开始。若下标指定从1开始，则要相应地调整映射关系。

3. 三对角矩阵#

若 $n$ 阶矩阵 $A$ 中的任意元素 $a_{ij}$，当 $|i-j| > 1$ 时均有 $a_{ij} = 0$($1 \leq i, j \leq n$)，则称为三对角矩阵。非零元素仅集中在以主对角线为中心的 3 条对角线的区域。

可将三对角上的元素按行优先顺序存入一维数组 B，且 $a_{1,1}$ 存于 B[0]。

三对角上的元素 $a_{ij}$($1 \leq i, j \leq n, |i-j| \leq 1$)在一维数组 B 中的下标 $k = 2i + j - 3$。

反之，已知元素存于B[k]中时，$i = \lfloor (k+1)/3 \rfloor + 1$，$j = k-2i+3$。例如，当 $k=0$ 时，$i = \lfloor (0+1)/3+1 \rfloor = 1$，$j = 0-2 \times 1+3=1$，存放的是 $a_{1,1}$；当 $k=2$ 时，$i = \lfloor (2+1)/3+1 \rfloor = 2$，$j = 2-2 \times 2+3=1$，存放的是 $a_{2,1}$；当 $k=4$ 时，$i = \lfloor (4+1)/3+1 \rfloor = 2$，$j = 4-2 \times 2+3=3$，存放的是 $a_{2,3}$。