数据结构：矩阵
- 矩阵是由m 行 n 列元素排列成的二维矩形数组，是线性代数和计算机科学中基础的数据结构。在编程中，矩阵通常用于表示二维数据（如图像像素、邻接矩阵）、线性变换、方程组等场景。
- 资料：
https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf
一、矩阵的定义与表示
1. 数学定义
一个m×n 矩阵（m 行 n 列）可表示为：
A=[a11a12…a1na21a22…a2n⋮⋮⋱⋮am1am2…amn] A = \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{bmatrix}A=a11a21⋮am1a12a22⋮am2……⋱…a1na2n⋮amn
其中aija_{ij}aij表示矩阵第iii行第jjj列的元素，矩阵的维度记为m×n。
2. 编程中的存储方式
在计算机中，矩阵的存储主要有两种方式：
- 二维数组（行优先存储）：最常用的方式，如 Python 的
list[list]、Java 的int[][]，按行顺序存储元素，访问a[i][j]的时间复杂度为O(1)O(1)O(1)。 - 一维数组映射：将二维矩阵映射到一维数组，通过公式
index = i * n + j（行优先）或index = j * m + i（列优先）计算元素位置，适合底层内存优化。
二、矩阵的核心分类
根据元素分布和维度特征，矩阵可分为以下常见类型：
- 方阵：行数和列数相等（m=n）的矩阵，如 3×3 矩阵。方阵可定义对角线元素（aiia_{ii}aii）、上三角矩阵（对角线下方元素全为 0）、下三角矩阵（对角线上方元素全为 0）。
- 单位矩阵：一种特殊的方阵，对角线元素全为 1，其余元素全为 0，记为III。例如 3×3 单位矩阵：
I3=[100010001] I_3 = \begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}I3=100010001 - 零矩阵：所有元素均为 0 的矩阵，记为OOO。
- 对称矩阵：满足aij=ajia_{ij}=a_{ji}aij=aji的方阵，其转置等于自身（AT=AA^T=AAT=A）。
- 稀疏矩阵：大部分元素为 0 的矩阵，通常用三元组（行号, 列号, 值）或十字链表存储，节省空间。
三、矩阵的核心操作
1. 基础操作
| 操作 | 描述 | 时间复杂度 |
|---|---|---|
| 访问元素 | 获取第 i 行第 j 列的元素 | O(1)O(1)O(1) |
| 矩阵转置 | 将矩阵的行和列互换，得到ATA^TAT，满足AT[i][j]=A[j][i]A^T[i][j] = A[j][i]AT[i][j]=A[j][i] | O(m×n)O(m×n)O(m×n) |
| 矩阵加法 | 两个同维度矩阵对应位置元素相加，要求AAA和BBB均为 m×n 矩阵 | O(m×n)O(m×n)O(m×n) |
| 标量乘法 | 矩阵中所有元素乘以一个常数 k | O(m×n)O(m×n)O(m×n) |
2. 矩阵乘法
矩阵乘法是矩阵的核心操作，仅当第一个矩阵的列数等于第二个矩阵的行数时可乘。
- 若AAA是m×pm×pm×p矩阵，BBB是p×np×np×n矩阵，则乘积C=A×BC=A×BC=A×B是m×nm×nm×n矩阵，其中：
C[i][j]=∑k=0p−1A[i][k]×B[k][j] C[i][j] = \sum_{k=0}^{p-1} A[i][k] × B[k][j]C[i][j]=k=0∑p−1A[i][k]×B[k][j] - 时间复杂度：O(m×p×n)O(m×p×n)O(m×p×n)，是算法优化的重点（如 Strassen 算法可优化至O(n2.81)O(n^{2.81})O(n2.81)）。
3. 特殊操作
- 矩阵求逆：仅方阵可逆时存在逆矩阵A−1A^{-1}A−1，满足A×A−1=IA×A^{-1}=IA×A−1=I，常用于解线性方程组。
- 行列式计算：仅适用于方阵，是衡量矩阵是否可逆的重要指标，记为det(A)det(A)det(A)。
四、矩阵的实现示例（Python）
classMatrix:def__init__(self,data):"""初始化矩阵，data为二维列表"""self.data=data self.rows=len(data)self.cols=len(data[0])ifself.rows>0else0def__str__(self):"""矩阵的字符串表示"""return'\n'.join([' '.join(map(str,row))forrowinself.data])deftranspose(self):"""矩阵转置"""transposed=[[self.data[j][i]forjinrange(self.rows)]foriinrange(self.cols)]returnMatrix(transposed)defadd(self,other):"""矩阵加法，要求维度相同"""ifself.rows!=other.rowsorself.cols!=other.cols:raiseValueError("矩阵维度不匹配，无法相加")result=[]foriinrange(self.rows):row=[self.data[i][j]+other.data[i][j]forjinrange(self.cols)]result.append(row)returnMatrix(result)defmultiply(self,other):"""矩阵乘法，要求self.cols == other.rows"""ifself.cols!=other.rows:raiseValueError("矩阵维度不匹配，无法相乘")result=[]foriinrange(self.rows):row=[]forjinrange(other.cols):# 计算C[i][j] = sum(A[i][k] * B[k][j])val=sum(self.data[i][k]*other.data[k][j]forkinrange(self.cols))row.append(val)result.append(row)returnMatrix(result)# 使用示例if__name__=="__main__":# 初始化两个矩阵A=Matrix([[1,2,3],[4,5,6]])# 2×3矩阵B=Matrix([[7,8],[9,10],[11,12]])# 3×2矩阵C=Matrix([[1,2],[3,4]])# 2×2矩阵print("矩阵A:")print(A)print("\n矩阵A的转置:")print(A.transpose())print("\n矩阵C + C:")print(C.add(C))print("\n矩阵A × B:")print(A.multiply(B))五、矩阵的典型应用
- 图的存储：用邻接矩阵表示图的顶点关系，如无权图用 0/1 表示边的存在，加权图用权重值表示。
- 图像处理：图像的每个像素对应矩阵的一个元素，矩阵的变换（如旋转、缩放）可实现图像的几何变换。
- 线性代数计算：解线性方程组、特征值分析、线性变换（如旋转矩阵、投影矩阵）。
- 动态规划优化：如 Floyd-Warshall 算法用矩阵存储任意两点间的最短路径。
- 机器学习：神经网络的权重参数、卷积核均以矩阵形式存储，矩阵乘法是前向传播的核心计算。
六、稀疏矩阵的优化存储
对于稀疏矩阵（大部分元素为 0），直接用二维数组存储会浪费大量空间，常用以下优化方式：
- 三元组存储：用列表存储所有非零元素的
(行号, 列号, 值)，例如矩阵[[0,2,0],[3,0,0],[0,0,5]]可存储为[(0,1,2), (1,0,3), (2,2,5)]。 - 十字链表：用链表同时按行和列存储非零元素，适合频繁插入/删除非零元素的场景。
)