矩 阵 压 缩

1. 对称矩阵压缩

$$\left[\begin{array}{ccccc}a& x& x& x& x\\ x& b& x& x& x\\ x& x& c& x& x\\ x& x& x& d& x\\ x& x& x& x& e\end{array}\right]$$

$$\left[\begin{array}{ccccc}a& & & & \\ x& b& & & \\ x& x& c& & \\ x& x& x& d& \\ x& x& x& x& e\end{array}\right]$$

二维数组中$a_{ij}$在一维数组中的下标:
$$k=i(i-1)/2+j-1$$

对于对称矩阵我们可以只保存下三角（包括对角线上的元素），或上三角的元素

原来需要的存储单元个数 $n\times n$ 变成了$(n(n+1)/2)$

2. 上下三角矩阵压缩

2.1 下三角对称矩阵压缩

对于
$$\left[\begin{array}{ccccc}{a}_{11}& & & & \\ a_{21}& a_{22}& & & \\ a_{31}& a_{32}& a_{33}& & \\ a_{41}& a_{42}& a_{43}& a_{44}& \\ a_{51}& a_{52}& a_{53}& a_{54}& a_{55}\end{array}\right]$$
将
$$\left[\begin{array}{ccccc}{a}_{11}& & & & \\ ...& & & & \\ a_{i1}& ...& a_{ij}& ...& \\ ...& & & & \\ a_{n1}& ...& a_{nj}& ...& a_{nn}\end{array}\right]$$
转化为
$$\left[\begin{array}{cccccccccccc}{a}_{11}& ...& a_{i1}& ...& a_{ij}& ...& a_{n1}& ...& a_{nj}& ...& a_{nn}& \end{array}\right]$$
原矩阵中的下标$i,j$，对应于数组中的下标$k$

2.2 上三角对称矩阵压缩

对于
$$\left[\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& a_{14}\\ & a_{22}& a_{23}& a_{24}\\ & & a_{33}& a_{34}\\ & & & a_{44}\end{array}\right]$$
将
$$\left[\begin{array}{ccccc}{a}_{11}& ...& a_{1j}& ...& a_{1n}\\ & & ...& & ...\\ & & a_{ij}& ...& a_{in}\\ & & & & ...\\ & & & & a_{nn}\end{array}\right]$$
转化为
$$\left[\begin{array}{cccccccccccc}{a}_{11}& ...& a_{1j}& ...& a_{1n}& ...& a_{ij}& ...& a_{in}& ...& a_{nn}& \end{array}\right]$$
原矩阵中的下标$i,j$，对应于数组中的下标$k$

即:
$$k=(i-1)(2n-i+2)/2+j-i$$

2. 对角矩阵压缩

将矩阵
$$\left[\begin{array}{ccccc}{a}_{11}& a_{12}& 0& 0& 0\\ a_{21}& a_{22}& a_{23}& 0& 0\\ 0& a_{32}& a_{33}& a_{34}& 0\\ 0& 0& a_{43}& a_{44}& a_{45}\\ 0& 0& 0& a_{54}& a_{55}\end{array}\right]$$
压缩为一维矩阵
$$\left[\begin{array}{ccccccccccccc}{a}_{11}& a_{12}& a_{21}& a_{22}& a_{23}& a_{32}& a_{33}& a_{34}& a_{43}& a_{44}& a_{45}& a_{54}& a_{55}\end{array}\right]$$
原来$n\times n$个存储单元现在只要$3n-2$个

原矩阵中的下标$i,j$，对应于数组中的下标$k$

即
$$k=2i+j-3$$
已知$k$:
$$\{\begin{array}{l}i=\lfloor (k+1)/3\rfloor +1\\ j=k-2i+3\end{array}$$