上三角矩阵、下三角矩阵、对称矩阵压缩存储所需一维数组大小为多少

对于一个 $n \times n$ 的上三角矩阵，它的压缩存储需要的一维数组大小为 $(n+1) \times n / 2$。因为上三角矩阵中，包含对角线上的元素一共有 $n$ 行，每行元素个数从 $1$ 开始递减，最后一行只有 $1$ 个元素，所以总共有 $1 + 2 + \cdots + n = n(n+1)/2$ 个元素，而压缩存储中不需要存储对角线以下的元素，所以数组大小为 $(n+1) \times n / 2$。

对于一个 $n \times n$ 的下三角矩阵，它的压缩存储需要的一维数组大小也为 $(n+1) \times n / 2$。因为下三角矩阵中，包含对角线上的元素一共有 $n$ 行，每行元素个数从 $n$ 开始递减，最后一行只有 $1$ 个元素，所以总共有 $n + (n-1) + \cdots + 1 = n(n+1)/2$ 个元素，而压缩存储中不需要存储对角线以上的元素，所以数组大小为 $(n+1) \times n / 2$。

对于一个 $n \times n$ 的对称矩阵，它的压缩存储需要的一维数组大小为 $n(n+1) / 2$。因为对称矩阵中，对角线上的元素只有 $n$ 个，而对角线两侧的元素个数相同，所以总共有 $n + 2 \cdot (n-1) + \cdots + 2 \cdot 1 = n(n+1)/2$ 个元素，而压缩存储中只需要存储对称轴上方的元素或下方的元素，所以数组大小为 $n(n+1) / 2$。

相关问题

设计算法将对称矩阵、三角矩阵、对角矩阵压缩存储到一维数组中（c++语言）

为了高效地压缩存储对称矩阵、三角矩阵和对角矩阵，我们可以利用它们特殊的结构。这里以C++为例，给出一种可能的方法：

1. 对称矩阵（Symmetric Matrix）[^4]:
对称矩阵的上半部分（包括对角线）已经包含了所有非对角元素，所以可以只保存其中的一半。例如，对于一个N×N的对称矩阵，可以存储从下标0到(N-1)/2的行和列。

   std::vector<int> compressSymmetricMatrix(int N, const std::vector<std::vector<int>>& matrix) {
       std::vector<int> compressed(N * (N + 1) / 2);
       int index = 0;
       for (int i = 0; i < N; ++i) {
           for (int j = i; j < N; ++j) {
               compressed[index++] = matrix[i][j];
           }
       }
       return compressed;
   }   

2. 上三角矩阵（Upper Triangular Matrix）[^5]:
只需存储主对角线上的元素和上三角区域的元素。同样，可以通过迭代来填充压缩后的向量。

   std::vector<int> compressUpperTriangularMatrix(const std::vector<std::vector<int>>& matrix) {
       std::vector<int> compressed(matrix.size());
       int index = 0;
       for (int i = 0; i < matrix.size(); ++i) {
           for (int j = i; j < matrix[i].size(); ++j) {
               compressed[index++] = matrix[i][j];
           }
       }
       return compressed;
   } 

3. 对角矩阵（Diagonal Matrix）[^6]:
对角矩阵的非对角元素全为0，所以只需要存储对角线上的元素。

   std::vector<int> compressDiagonalMatrix(const std::vector<std::vector<int>>& matrix) {
       std::vector<int> compressed(matrix.size());
       for (int i = 0; i < matrix.size(); ++i) {
           compressed[i] = matrix[i][i];
       }
       return compressed;
   } 

将 10 阶对称矩阵压缩存储到一维数组 A 中，则数组 A 的长度最少为

一个 $n$ 阶对称矩阵中，对角线元素有 $n$ 个，上三角（不含对角线）的元素有 $n(n-1)/2$ 个，因为对称矩阵的对角线以下的元素和对角线以上的元素是相同的，所以只需要存储其中一部分。

因此，一个 $n$ 阶对称矩阵的元素总数为 $n+n(n-1)/2=(n^2+n)/2$。

而对称矩阵的一维数组压缩存储只需要存储对称矩阵的下三角（不含对角线）的元素，数量为 $n(n-1)/2$ 个，因此数组 A 的长度最少为 $(n^2+n)/2-(n(n-1)/2)=n(n+1)/2$。

因此，将 10 阶对称矩阵压缩存储到一维数组 A 中，数组 A 的长度最少为 $10 \times (10+1)/2 = 55$。