主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
浅谈矩阵
最后更新于 2025-07-31 11:01:02
作者
Strange_qwq
分类
算法·理论
复制 Markdown
查看原文
删除文章
更新内容
$$ \lceil \text{学前班} \rfloor \hspace{0.2 cm} \text{线性代数基础} $$ ### 矩阵的定义 ### 矩阵的基本运算 ### 矩阵的变换 d定义n个变元,$ x_1,x_2,x_3...x_n$ 的线性方程。 $$ \begin{cases} a_{11}x_1+a_{12}x_2+...a_{1n}x_n\\ a_{21}x_1+a_{22}x_2+...a_{2n}x_n\\ ...\\ a_{m1}x_1+a_{m2}x_2+...a_{mn}x_n\\ \end{cases} $$ ### 高斯消元 ### 行列式 定义 $P_n$ 表示 $n!$ 个长度为 $n$ 的排列 $p$ 构成的集合。矩阵的行列式定义为 $$ |A| \sum_{p \in Pn}{sgn(p)} \prod_{i=1}^{n} a_{i,{p_i}} $$ 其中 $sgn(n)$ 表示 $ -1^{排列逆序对的个数} $,设 $ N(p) $ 表示 $p$ 的逆序对个数,则 $sgn(n)=-1^{N(p)}$ ### 矩阵树定理 矩阵树定理 $(Matrix-tree Theoerm)$ 是把图的生成树个数和矩阵行列式联系起来的定理 #### 有向图内向生成树计数 对于无自环 (允许有重边) 的有向图 $G=(V,E)$。设出度矩阵 $D(G)$ 表示每个点的出度的对角矩阵 ( $d_{ii}$ 表示结点 $i$ 的出度,其余位置为 0)。而 $A(G)=\begin{bmatrix} a_{ij} \end{bmatrix}$ 表示邻接矩阵,$a_{ij}$表示 $ (i \to j) $ 的边数。那么可得到对应的拉普拉斯矩阵$(Laplacian Matrix) \hspace{0.2cm}L(G)=D(G)-A(G)$ #### 证明 $L(G)=D(G)-A(G)$ 需证明两件事 + $|L(G)|$ 的组合意义是通过容斥计算 $G$ 的只有平凡环的基环内向森林生成个数 + $|L(G)_{k,k}|$ 的组合意义是通过容斥计算 $G$ 以 $k $ 为根的内向生成树的个数 称自环是平凡的环 注: 如果一个图没有自环,那么它是不存在只有平凡环的基环内向生成森林,也就是对于简单的有向图,$ |L(G)|=0 $ 。 拆成两部分考虑: $$ sgn(p)\prod_{i=1}^n{a_{i,p_i}}=sgn(p)\prod_{i\not } $$
正在渲染内容...
点赞
0
收藏
1