矩阵入门

什么是矩阵

在数学中，矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合，最早来自于方程组的系数及常数所构成的方阵(摘自某百科)

(n) 行 (m) 列的矩阵大概长这个样子 :

[A = left[egin{array}{c} a_{1,1}&a_{1,2}&cdots&a_{1,m}\ a_{2,1}&a_{2,2}&cdots&a_{2,m}\ a_{3,1}& a_{3,2}&cdots&a_{3,m}\ cdots&cdots& &cdots\ a_{n,1}& a_{n,2}&cdots&a_{n,m} end{array} ight] ]

这 (n imes m) 个数称为矩阵 (A) 的元素，简称为元

数 (a_{i,j}) 位于矩阵的第 (i) 行第 (j) 列

定义一个矩阵类 :

struct matrix {
	int r, c; // 矩阵的行与列
	int a[N][M];
	inline matrix(int _r = 0, int _c = 0) {
		r = _r, c = _c;
		memset(a, 0, sizeof a);
	}
}

矩阵的基本运算

加法

注意 : 只有相同大小的矩阵才可以相加

[left[egin{array}{c} 1&4\ 3&2 end{array} ight] + left[egin{array}{c} 4&2\ 5&7 end{array} ight] = left[egin{array}{c} 5&6\ 8&9 end{array} ight] ]

代码实现 :

matrix add(matrix A, matrix B) {
	matrix C(A.r, A.c);
	for(int i = 0; i < C.r; ++i) // 枚举矩阵 C 的行
	  for(int j = 0; j < C.c; ++j) // 枚举矩阵 C 的列
	  	C.a[i][j] = A.a[i][j] + B.a[i][j];
	return C;
}

矩阵的加法满足交换律和结合律

即 :

(A + B = B + A)

((A + B) + C = A + (B + C))

减法

与加法类似，只有相同大小的矩阵才可以相减

数乘

设 (lambda) 为常数，矩阵数乘即把矩阵每一个数乘上一个 (lambda)

[2 imes left[egin{array}{c} 1&4\ 3&2 end{array} ight] = left[egin{array}{c} 2&8\ 6&4 end{array} ight] ]

矩阵数乘满足结合律和分配率

即 :

(lambda(mu A) = mu(lambda A))

(lambda (mu A) = (lambda mu)A)

((lambda + mu)A = lambda A + mu A)

(lambda (A + B) = lambda A + lambda B)

矩阵的加减法和矩阵的数乘合称矩阵的线性运算

~~其实感觉矩阵加减法只是做了 n * m 次普通的加减法~~

乘法

重点，很有用

两个矩阵的乘法当且仅当第一个矩阵 (A) 的列数，和另一个矩阵 (B) 的行数相等时才能定义

如 (A) 是 (n imes m) 的矩阵，(B) 是 (m imes p) 的矩阵，它们的乘积 (C) 是一个 (n imes p) 的矩阵

它的一个元素 :

[c_{i, j} sum_{k = 1}^{m}a_{i, k} b_{k, j} ]

代码实现 :

matrix mul(matrix A, matrix B) {
	matrix C(A.r, B.c);
	for(int i = 0; i < C.r; ++i) // 枚举矩阵 C 的行
	  for(int j = 0; j < C.c; ++j) // 枚举矩阵 C 的列
		for(int k = 0; k < A.c; ++k) // 上面式子中 k = A.c
		  C.a[i][j] += A.a[i][k] * B.a[k][j];
	return C;
}

注意 : 矩阵的乘法不满足交换率，但满足结合率和分配率

即 :

(A B eq B A)

((A B) C = A (B C))

((A + B)C = AC + BC)

(C(A + B) = CA + CB)

快速幂

由于矩阵乘法具有结合率，当我要计算一个矩阵的 (n) 次方时，可以运用到快速幂的思想

[A^n = left{egin{array}{l}A^{lfloorfrac n 2 floor} cdot A^{lfloorfrac n 2 floor} & k是偶数 \A^{lfloor frac n 2 floor} cdot A^{lfloorfrac n 2 floor} cdot A & k是奇数end{array} ight. ]

原来乘法求 (A^n) 的复杂度是 (O(s^3n)) // (s) 为矩阵大小

现在只要 (O(s^3logn)) 就可以求 (A^n) 了

代码实现 :

matrix mat_fpm(matrix bs, int mi) {
	matrix res = e; // e 为单位矩阵 (主对角线全 1)
	while(mi) {
		if(mi & 1) res = mul(res, bs);
		bs = mul(bs, bs), mi >>= 1;
	}
	return res;
}

模板 : 洛谷P3390