矩阵论

第一章

核域（解空间）、值域？

n(A) = dim N(A) = n - rank(A)
n(A):核空间的维数，也称为零度

rank(A) = dim R(A)

证是否为线性空间、子空间

加法封闭性
数乘封闭性
八条性质（重点是零元、负元）

任何一个元素 + 零元 等于其本身
任何一个元素 + 负元 等于 零元

博客：（2）

• 非空
• 加法、数乘封闭
• 八条性质？

求一个向量关于一组基的坐标

列出方程等式 再进行求解

求过渡矩阵

求子空间的基？

求子空间的维数？

重点：（5）线性子空间

解空间的基、维数？

习题1 第6题

第二章

记住 施瓦茨不等式

内积定义的证明？

四个条件：
对称性
结合性
数乘
非负

内积、模

(a,a) = |a|^2

齐次方程解法、非齐次方程解法

求标准正交积！！

前提是找出一组基
再进行正交化

向量的内积！！

(a,a) = a^T a

第三章

线性变换在基下的矩阵？

线性变换的核域、值域！

（11）：线性变换的矩阵表示

线性变换的特征值、特征向量！

找出这个线性变换对于的矩阵A
求A进行变换 求解 找出初等解系
记得设特征向量（基础的）

特征值与特征向量的关系

求矩阵的标准形！

就是求 smith标准形
12）：相似形理论

一般还是 先求 D1 D2 D3
再求出d1 d2 d3

证明两个矩阵相似（难点！！）

习题三 例题13

（12）：相似形理论

定理3.3.11

• 两个矩阵相似
• 与一个对角阵相似

证明方阵相似于对角阵

（13）：Hamliton-Cayley定理、最小多项式

m(\lambda)无重根

求若当标准形J（难点！）

习题三 15题

找初等因子

求相似变换矩阵P 使得PAP^{-1} = J（难点！）

利用Hamliton-Cayley定理 简化算式

习题三 题23

求最小多项式

线性变换定义

等价

补充

难题

• 课本 例题 P54 例12
• 习题三 P65 例16
• 习题三 P65 例4

概念

• 正定二次型

• 行列式因子、不变因子、初等因子

  行列式因子就是 D
  不变因子就是 d
  初等因子 就是 所有d中的因子（可能会有重复的）

• 伴随矩阵

• 多项式的幂

  (a+b)^k = ??

• 零化多项式

• 谱范数

  其实就是矩阵的 2 范数

• 单纯矩阵

  n阶方阵相似于对角阵 称其为单纯矩阵

• 实对称正定阵

  A = P^T P

第四章

向量范数的证明

非负性
齐次性
三角不等式

矩阵范数的证明

非负
齐次
三角不等式
相容性

向量范数

• 1范数
• 2范数
• ∞范数

矩阵范数（记忆！）

（15）：矩阵的范数

• m1范数

  A中每个元素先求模 再求和

• m∞范数

  n 乘以 最大元素的模

  注意这里的n是方阵的行数或列数

• F- 范数（m2范数）

  所有元素模的平方 再求和

  再对和进行开方

• 1范数

  对每一列元素取模再求和，然后找出各列模总和中最大的一个值

• 2范数

  找出A^{H}A中的最大特征值 再开方

• ∞范数

  对每一行元素取模再求和，然后找出各行模总和中最大的一个值

第五章

求矩阵的微分、积分

求e^At、G(A)

令需要求解的方程为G(A)
列出特征方程
求出d
从而得到 最小多项式m(\lambda)
再根据最小多项式设未知方程（这里次数要降一次）
一个未知数需要一个方程 方程数量不够利用微分求导来凑
求解方程组即可

• 方法一：对角？
• 方法二：若当？
• 方法三：待定系数

齐次微分方程组的解！

非齐次微分方程组的解！

第六章

LU分解（！）

A=LU

L：下三角矩阵
U：上三角矩阵

也称为A的三角分解

分解形式不唯一

• 可逆方阵的LU分解

  A=LU

  A的各阶顺序主子式不等于0

  有唯一的LU分解

  L：单位下三角矩阵 主对角元素全为1（注意这里是单位下三角）
  U：上三角矩阵

  求解过程：

  先对A进行初等行变换（右边补充单位阵E）

  使得左边变为上三角矩阵U

  然后再对右边求逆矩阵 得到L

• 可逆方阵的LDU分解

  A的各阶顺序主子式不等于0 则有唯一的LDU分解

  L：单位下三角
  U：单位上三角
  D：对角阵

  先对A扩充为增广矩阵(A,E)

  进行初等行变换 得到(A1,L1) 其中A1是上三角 L1是单位下角

  对L1求逆矩阵 得到L：单位下三角

  然后对A1再进行填充 得增广矩阵（这次是列填充）（A1｜E）

  然后进行初等列变换 使得A1变为对角阵 得到(D｜U1)

  D就是需要的对角阵

  然后再对U1进行求逆 得到U

• 不可逆方阵的拟LU分解

  • 引言：A可逆时 但顺序主子式不全为非0时

    对A的行进行重排 使得顺序主子式全为非0

    行重排 相当于 A左乘一个初等矩阵P

    再对PA进行LU分解或LDU分解

    即 PA=LU 或 PA=LDU

  • A不可逆时 即R(A)=r < n

    首先保证前r阶顺序主子式全非0

    然后再进行正常的LU分解（步骤一样）

    若前r阶顺序主子式有0时

    则需要先进行重排

    使得前r阶顺序主子式全非0

    再进行LU分解

• 不可逆方阵的拟LDU分解

  首先保证前r阶顺序主子式全非0

  然后再进行正常的LDU分解（步骤一样）

  若前r阶顺序主子式有0时

  则需要先进行重排

  使得前r阶顺序主子式全非0

  再进行LDU分解

谱分解

列出特征多项式
求解特征值
分别求出特征值对应的特征向量
所有特征向量组成P
求出P^{-1}
…

• 概念：单纯矩阵？

  方阵A可以相似于对角阵

• 概念：谱分解

• 重点：求A的谱分解

  列出A的特征多项式
  求出特征值
  求出特征值对应的特征向量
  组成P
  再求P^{-1}
  依据特征值对应的重根数划分P和P^{-1}
  得到S_i
  最后结果为\sum \lambda_i S_i

最大秩分解

A = CD

C：列满秩
D：行满秩

步骤：
先对A进行初等行变换 得行最简形A2
得到rank(A)=r
取A中前r列为C A2中前r行为D（易错：c是从A中取 D是从最简行矩阵中取！）

最大秩分解不唯一｜ A = CD 不唯一

但D^H (DD^H){-1} (C^{H}C){-1}C^{H} 唯一

• 形式：A=CD
• 重点：化为行最简形

QR分解

先进行最大秩分解
对C进行标准正交化 得到Q
利用A=QR 变形 R= Q^{H}A 得到R

因为A=CD不唯一 故A=QR也不唯一

• 形式：A=QR

  Q^{H}Q = E
  rank® = r = rank(A) 说明R是行满秩

• 注意：列满秩和行满秩的情况

  列满秩时（一般是这样 高个子）
  A = QR
  Q^{H} Q = E
  R为具有正对角元素的上三角阵
  R : r * r

  行满秩（矮个子）
  A = LQ
  Q^{H}Q = E
  L: m * r
  L为具有正对角元素对下三角阵

• R的求法?

  A = QR
  Q^H Q = E
  =>
  R = Q^H A

第七章

A-

AGA = A

称G为A的广义逆矩阵

G = A^(i) \in A{i}

A^(i)：满足第i个方程的一个矩阵
A{i}：满足第i个方程的所有矩阵

A{1} 就是A-

A-不唯一

• A- 推导

• A- 求解过程（重点！）

  对A进行初等行、列变换
  用P、Q分别记录其变换过程

  最后 A = Q X P

  其中X是大小是和原来A相反的
  比如A是3 * 4 则X为 4 * 3

  除了E_r外，其他用变量填充

• A-的性质

  • 左逆
  • 右逆

A+

先将A进行最大秩分解为 A = CD

再代入A+公式进行计算

相容线性方程组的通解

• 形式1

  A- y + (E - A- A )z

• 形式2

  A+ y + (E - A+ A) z

相容线性方程组的最小范数解（必考）

A+y

不相容线性方程组的最小二乘解

A_{l}^{-}y 是最小二乘解

A_{l}^{-} \in A{1,4}

不相容线性方程组的极小最小二乘解（必考）

A+y

第八章

特征值上界?

• 复矩阵
• 实矩阵

圆盘定理?

• 行对角占优
• 列对角占优

盖尔定理

谱半径的估计?

---

图论

第一章

图的三要素

握手定理

同构？

• 定义
• 判定??

图运算

• 删点运算
• 删边运算
• 并运算
• 交运算
• 差运算？
• 对称差（或环和运算）

图的矩阵表示

• 邻接矩阵

  • 无向图的邻接矩阵
  • 有向图的邻接矩阵
  • 加权有向图的带权邻接矩阵

• 关联矩阵？?

  • 无向图的关联矩阵
  • 有向图的关联矩阵

• 边矩阵

第二章

通路、道路、路径的定义？?

连通？

• 顶点之间的连通???
• 图连通
• 连通片??

圈

• 定义

• 长度？

  • 奇圈
  • 偶圈

顶点之间的距离

有向通路

• 有向道路

• 有向路径

  • 有向圈

• 有向回路

半通路

强连通、单向连通、弱连通

有向图中

• 完备回路
• 完备通路
• 完备半通路

强连通片（或强连通分图）

树

• 定义
• 树叶
• 森林或林
• 平凡树

生成树？

生成树的个数

Caylay公式

生成树算法

• 破圈法
• 避圈法

最小生成树

• 定义

• 算法

  • Kruskal算法

    先边按权从小到大排列
    再从小到大选 不构成圈即可

  • Prim算法

第三章

点断集

• 定义？

• 连通度？

  最小点断集中顶点的数目

  • 有点断集
  • 无点断集
  • 不连通
  • 平凡

• 割点

• k-连通图

边断集

• 定义

• 边连通度

  • 有边断集
  • 无边断集
  • 不连通
  • 平凡

• 割边

• k-边连通图

门格尔定理（Menger）？?

课本 P39

Whiteney定理？???

课本 P39

割边

割集？？

割点

Harary算法？

课本 P45

概念

无向图、有向图、混合图

环、重边

简单图

完备图（K_n）

完备二部图（K_{m, n}）

平凡图

空图

边集为空

n阶图

顶点数为n

(n,m)图

顶点数为n 边数为m

边的重数

连接两个相同顶点的边的数量

子图

顶点、边都是原顶点、边的子集

生成子图

顶点保留原图顶点 边取子集

顶点导出子图、边导出子图

K-正则图

每个顶点的度数都是k

正则图的阶数

阶数就是顶点数

偶图

其实就是二部图

图的直径

两顶点之间的最大距离

未掌握/易错

二部图的充要条件

G不含奇圈

G是树的充要条件？

（5）

• G无环…

  且任何两个顶点之间有唯一的路径

• G连通…

  E = V - 1

• G连通…

  且对G的任一边，G-e不连通

• G无圈…

  且 E = V - 1

• G无圈…

  对任意一个e = uv \notin E(G) G+e恰好有一个圈

G是连通图，e \in E， 则e是割边的充要条件？

e不含在圈中

G连通的充要条件？

G有生成树

G连通，G是树的充要条件

G的每条边都是G的割边

设T是连通图G的一颗生成树，对T的每条边e有

余树 T- 不含 G的割集
T-+e 含G的唯一割集

树T的顶点v是T的割点的充要条件

d(v) >= 2

一个图有理想匹配的必要条件

偶数个顶点

四定理

H图的充分、必要、充要条件

• 必要条件
• 充分条件
• 充要条件

图同构的必要条件

两图的顶点数、边数相等
次数相同的顶点数也相等

G是非空连通图

P109

• G是欧拉图
• G无奇次顶点
• …

G有欧拉道路的充要条件

G最多只有两个奇次顶点

G是可嵌平面图的充要条件

G可在球面上嵌入

• answer - 1

  G在球面上可嵌入

• answer - 2

  不含K5 k3 3 的任何细分

G是平面图的充要条件

G中无可收缩到K5 或 K33 的子图

计算题

Dijkstra算法

Floyd算法

匈牙利算法

• 求理想匹配
• 求最大匹配

Kuhn-munkres算法

P86

求最大权理想匹配

若需要求最小权理想匹配 使用一个大数减去所有元素

寻找欧拉巡回

寻找一个权最小的巡回

• 是欧拉图时

  • Fleury算法
  • Hierholzer算法

• 不是欧拉图时

  • 正好有两个奇次顶点

  • 最小对集法（2n个奇次顶点）

    P117

    求出奇次顶点的最短距离
    寻找奇次顶点的最小权匹配 （注意使用大数减去 一般就枚举就可以了）
    将M添加至原图G
    求欧拉巡回

TSP近似算法

• Christofides最小权匹配算法

  P134

• 二边逐次修正法

  P142

• 求最佳H圈的权的下界

  P143

可平面化算法

P164

证明方法

最长路径法

数学归纳法

• 第一类
• 第二类

第四章

Dijkstra算法

Floyd算法

第五章

匹配？

• 定义？？?
• M渗透点？？
• M非渗透点？？
• M交错路径？？?
• M可增长路径？？

理想匹配？？

最大匹配？？?

四定理

• Berge定理
• Hall定理？？?
• Konig定理？？?
• Tutte定理？？

t条件？？

覆盖???

极小覆盖???

最小覆盖???

第六章

欧拉图

• 无向欧拉图

  • 巡回？？
  • 欧拉巡回
  • 欧拉图
  • 欧拉道路

• 有向欧拉图

  • 有向巡回
  • 有向欧拉巡回
  • 有向欧拉图
  • 有向欧拉道路

• Fleury算法？

• Hierholzer算法？

• 最小对集算法 Edmonds算法（重点）

哈米尔顿图？？

• H路径???

• H圈???

• 定义

• 必要条件

• 充分条件

  • Dirac定理

• 充要条件？？？

  • 定理6.7
  • 定理6.8

• 图的闭包

流动推销员问题

• 最佳H圈？？

  权最小的哈米尔顿圈

• 最佳推销员回路？？？

  经过每个顶点至少一次的权最小闭通路

TSP近似算法

• 构造型

  • Christofides最小权匹配算法

• 改进型

  • 二边逐次修正法

• 求最佳H圈的下界

第七章

平面图

• 可嵌平面图

  图G可以嵌入平面

• G的平面嵌入

  可嵌平面图G 嵌在平面中形成的图 称为G的平面嵌入

欧拉公式

• 面的定义？？

• 面集

• 面的数目

• 面的周界？？

  顶点 + 边

• 欧拉公式表示

对偶图

• 画法？

• 面f的次数？？

  周界中边的数目
  割边算两次！

库拉托夫斯基定理

• K5 和 K(3,3) 都是非平面图

• 细分？？？

  将G的某些边换成路径

• 可嵌平面图的充分必要条件（库拉托夫斯基定理）？？

• 初等收缩？？

• 瓦格纳定理？？

可平面性算法

• 桥？？？

  • 定义
  • 附着点
  • 基

• 可嵌平面图

• 可嵌平面子图

• G-可接受的平面嵌入

• 可展？？

• 可平面性算法（重点）

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/125247523