密码学基础之线性代数Ⅰ

线性代数可以说是当初我进入大学遇到的第一个坎了,由于大一上课时没有认真听讲,觉得什么矩阵、行列数、秩等等各种概念都过于抽象,学的就不是很好,最后也是靠死记硬背应付过了考试。但后来接触 CTF,接触密码学,才发现线性代数是非常优雅的一门学科,同时也是非常重要的工具。

但这篇文章我并不打算教授大家各种专业的线性代数知识,证明什么定理之类的。首先我自身水平有限(其实很差)是其一,我显然是不如大学里专门教授线性代数的老师的;另外单单凭这么一篇简短的文章就想让大家学会这么重要的一门学科也无异于是痴人说梦。

这篇文章更像是一份学习笔记,学习的是 3Blue1Brown 的线性代数视频 【官方双语/合集】线性代数的本质 - 系列合集_哔哩哔哩_bilibili,这个系列 3b1b 从几何的角度,搭配精致的动画制作,非常直观而形象的向我们介绍了线性代数之美。真的,对于想要学习线代、理解线代;不管是真的喜欢,还是为了应付考试的同学,我都强烈!强烈!强烈推荐这个系列的视频。

(为了弥补视频所忽略的数值运算,我会在每一节最后给出与该节主题相关的 sagemath 代码)

[TOC]

00 序言

image-20230905101239386

也许在大学中,我们主要关注于线性代数中的各种计算,比如行列式、叉积、矩阵乘法。但这个系列我们主要想解决很多为什么。为什么矩阵乘法如此定义,为什么叉积和行列式有关,特征值又代表着什么。我们忽略数值运算,但是从几何直观的角度向大家介绍线性代数。这不是说数值运算不如几何直观重要,他们各有所长。几何直观能够让我们判断在各种情况下应该用何种工具,数值运算则能够是我们顺利的使用这些工具。

而这个系列的目标不是通过区区几个视频就让大家学会一门完整的科目,但希望能帮助大家形成正确的几何直观,以有助于后续更进一步的学习。

01 向量究竟是什么?

image-20230905102756882

向量是线性代数中最基础的组成部分,

物理学中决定一个向量的仅仅是它的长度和所指的方向,与它所在的起始点无关。

计算机中向量是有序的数字列表如 $[0 \ 1]$ ,列表中的元素决定里向量的维度。

在数学中,向量则可以是成任何东西,只要保证两个向量相加以及与数字相乘是有意义的即可。(这个观点就比较抽象了,会在系列的最后一节说明)

在这里,我们暂且将向量考虑为一个箭头,它落在某个坐标系中,比如 x-y 平面,并且箭头的起点位于原点。考虑用数字去表示这个向量,例如我们有一个二维向量 $[2 \ 1]$, 2 则表示这个向量箭头的终点与 x 轴的距离 为 2,与 y 轴的距离为 1。 这样,一个向量和一个数组就一一对应了。

线性代数围绕两种基本运算:向量加法与向量数乘。

向量加法就是将表示两个向量的箭头头尾连接(将其中一个箭头的起点从原点挪到另一个箭头的终点),和向量就是从远点指向新终点的箭头。(可以看作是两个运动的复合)

image-20230905104112459

从数值角度看,向量相加就是将两个向量的对应项相加得到新的向量。

向量数乘 就是对一个向量进行缩放。如果这个数是负数,则还会反向。这些用于向量缩放的数,我们称之为标量

image-20230905104800824

从数值角度看,向量数乘就是将向量的每一个项和标量相乘

sagemath 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 定义向量
sage: a = vector([1,2])
sage: b = vector([6,2.3])

# 向量加法
sage: a + b
(7.00000000000000, 4.30000000000000)

# 向量数乘
sage: 5 * a
(5, 10)
sage: 2.2 * b
(13.2000000000000, 5.06000000000000)
sage:

02 线性组合、张成的空间与基

image-20230905131845526

在上一节中介绍了向量坐标例如 $[3 \ -2]$,现在我们要把这个向量的每个坐标看作是一个标量(也就是用来伸缩一个向量),然后在 xy 坐标系中,定义两个特殊的向量 $\hat i,\hat j$ 分别指向坐标轴的正方向(即xy坐标系的基向量),于是向量 $[3 \ -2]$ 就可以表示为 $3\hat i + (-2) \hat j$

image-20230905132416665

在这里,我们运用了 “缩放向量并且相加” 的技术。运用这样的技术, xy 坐标系中的任意一个向量均可以由 $\hat i, \hat j $ 来表示。

此时我们提出一个问题,如果选择不同的基向量会怎样?例如下图的 $v,w$

image-20230905132702023

显然通过 “缩放向量并且相加” 的技术,xy 坐标系中的任意一个向量也均可以由 $v,w$ 来表示。因此某一特定向量可以使用不同的基来描述,于是 每当我们用数字描述向量时,它都依赖我们正在使用的 (基的严格定义会在后面给出)。

两个数乘向量的和,被称为这两个向量的线性组合

image-20230905133105313

那么 “线性” 这个词从何而来,跟直线又有什么关系呢?姑且可以这么理解,如果固定一个标量,让另一个标量自由变化,所产生的向量的终点会描绘出一条直线

image-20230905133337648

大部分情况下,如果我们自由的变化两个向量的标量,那么我们能够得到整个平面中的所有向量;但是如果这两个向量是共线的话,那么所产的向量终点会被限制在一条过原点的直线上(事实上和这两条向量也是共线的);更极端的,可能这两个向量都是零向量,那么就只能呆在原点了。

我们称所有可以表示为给定向量线性组合的向量的集合,为给定向量张成的空间(span)

image-20230905134033125

于是我们用行话重新叙述刚才的内容,对于大部分二维向量来说,它们张成的空间是一个;但当它们共线时,它们张成的空间就是一条线;如果都是零向量,那么它们张成的空间就是一个

那么两个三维向量张成的空间是什么样的?三个三维向量呢?(可以看一下视频中 up 制作的动画,非常精美形象)

现在如果我们有多个向量,并且可以移除其中一个而不减小张成的空间,我们称它们是 “线性相关” 的。另一种描述方法就是,该向量($u$)可以表示为其他向量 $v,w$ 的线性组合。

image-20230905135030742

另一方面,如果所有向量都给张成的空间增添了新的维度,它们就被称为是 “线性无关”

现在我们可以给出前面所介绍过的 的严格定义

image-20230905135213284

sagemath

1
2
3
4
# 线性组合

sage: 5*a+2.2*b
(18.2000000000000, 15.0600000000000)

03 矩阵与线性变化

image-20230905135651059

这一节介绍了线性变换和矩阵的关系(建议初学者反复观看),首先我们解析一下 “线性变换” 这个词。

“变换”本质上是“函数”(接受输入,输出结果)的一种花哨的说法。在线性变化中,我们考虑的是接受一个向量并且输出一个向量的变换。“变换”一词在暗示我们用运动去思考问题。输入向量是怎么经过运动变换为输出向量的。

“线性”则要求变换满足两条性质,一是直线在变换后仍然保持为直线,二是远点必须保持固定。下面给出了三个不是线性变换的例子。

image-20230905140420110

image-20230905140502823

image-20230905140530841

总的来说,我们可以把线性变换看作是 保持网格线平行切等距分布 的变换。例如旋转,翻转。

那么如何用数值去描述线性变换呢?建议观看视频,这里给出结论:只需要记录两个基向量 $\hat i,\hat j$ 变换后的位置即可。 因为线性变换的原因,所有变换后的向量都可以按照原来的方式(标量不变)变换后的基向量表示。

image-20230905140956059

image-20230905141129067

矩阵乘法的法则也由变换后坐标的计算公式定义:我们设变换后的基向量 $\hat i = [ a \ c],\hat j = [b \ d]$,对于原任意向量 $[x \ y]$ 变换后的坐标计算规则就是 $x$ 乘以 $\hat i $, $y$ 乘以 $\hat j$ (因为我们前面提到,任意向量可以表示为标量数乘基向量的和,而线性变化中标量不会变化

image-20230905142206603

这里考虑一个特殊情况,如果变换矩阵的列线性相关,那么这个线性变换就会将整个二位空间挤压到它们所在的一条直线上

image-20230905143317261

总之,线性变换是操纵空间的一种手段, 它保持网格线平行且等距分布,并且保持原点不动。而这种变换只需要变换后基向量的坐标就可以表示。以这些坐标为列所构成的矩阵为我们提供了一种描述线性变换的语言,而矩阵向量乘法就是计算线性变换作用于给定向量的一种途径。 这里重要的一点是,每当我们看到一个矩阵时,都可以把它解读为对空间的一种特定变换

image-20230905144056406

sagemath

1
2
3
4
5
6
7
8
9
# 输入二维数组(行向量)构造矩阵
sage: Matrix([[1,3],[-2,0]])
[ 1 3]
[-2 0]

# 矩阵与向量相乘
sage: Matrix([[1,3],[-2,0]]) * vector([-1,2])
(5, 2)
sage:

04 矩阵乘法与线性变换复合

image-20230905144211073

当我们想要描述一个复合变换:即一个变换之后再进行一个变换 ,例如先逆时针旋转90°,然后剪切。那么从头到尾的总体作用则是另一个线性变换。(注意我们需要从右边往左边看,这可能和我们平时的阅读习惯相左)

image-20230905161319957

根据上一节的内容,我们同样可以通过追踪 $\hat i,\hat j$ 的坐标,来用矩阵完全描述这个复合变换。

image-20230905161516219

但两种方式表达的都是同一个变换,

image-20230905161602066

然后我们去掉等式两边的向量

image-20230905161802919

这里我们暂且不讨论具体的矩阵计算法则,但我们需要知道,两个矩阵相乘的几何意义:它意味着两个线性变换相继作用(需要注意变换顺序,从最右边的开始)。就像我们计算复合函数 $f(g(x))$ 时 ,我们总是先计算右边的 $g(x)$,然后再将结果输入到函数 $f$ 中最后得到输出。

image-20230905162017958

之所以我们强调阅读顺序,是因为变换的顺序会影响到结果。

如果先剪切,再旋转

image-20230905162807292

如果先旋转,再剪切

image-20230905162830270

可以看到,二者顺序不同,则总体效应明显不同。

因此我们知道,矩阵相乘不具有交换律。那么矩阵相乘有结合律么?即 $(AB)C \overset{?}= A(BC)$ 。几何直观的高光时刻

如果我们用数值计算去证明矩阵相乘具有结合律,那将会很麻烦,并且对我们毫无启发。但是如果我们考虑变换的相继作用呢?

$(AB)C=ABC$ 表示先进行 C 变换,再进行 B 变换,再进行 A 变换

$A(BC)$ 则表示先进行 C 变换,再进行 B 变换,再进行 A 变换

完全相同的过程,需要什么证明呢?

你可能觉得这不太正经,但这确实是矩阵乘法具有结合律的一个实实在在的证明。

sagemath

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
sage: A = Matrix([[1,3],[-2,0]])
sage: B = Matrix([[2,3],[-2,8]])
sage: C = Matrix([[11,-5],[9,3]])

# 矩阵乘法
sage: A*B
[-4 27]
[-4 -6]
sage: B*A
[ -4 6]
[-18 -6]

# 乘法结合律
sage: A*B*C
[199 101]
[-98 2]
sage: A*(B*C)
[199 101]
[-98 2]
sage: A*(B*C) == (A*B)*C
True

附注 1

image-20230905164914023

这个系列大部分是在平面中进行讨论,主要是因为平面更容易在屏幕中展现,也利于理解。而一旦我们掌握了二维空间里的核心概念,那么推广到更高维空间则是轻而易举的。

与二维空间下的平面一致,三维空间下的线性变换也可以通过追踪基向量来表示,由于多了一维,我们也需要引入一个新的指向 z 轴正方向的基向量 $\hat k$ 。

其余如复合线性变换等的数值计算和几何意义均与在二维下类似。值得一提的是三维矩阵在部分领域如计算机图形学、机器人学有着非常重要的作用。

05 行列式

image-20230905170959119

我们注意到前面的线性变换,有的将空间向外拉伸,有的则将空间向内挤压。那么,这个具体拉伸的量该如何测量呢?更具体一点,就是测量一个给定区域增大或者缩小的比例。

三张图说明这个过程

image-20230905171724971

image-20230905171742679

image-20230905171800063

面积由原来的1变成了6,所以我们说这个线性变换将它的面积变为了 6 倍。

而剪切矩阵看起来将空间往右挤压,但其实并不改变面积

image-20230905171923564

事实上,通过图中所示的黄色区域面积的变化,就能够知道其他任意区域的面积变化比例(线性变换的魅力)。而这个线性变换改变面积的比例,则称为这个变换的行列式

如果一个变换的行列式是 2,说明它将一个区域的面积增大为原来的两倍。

如果一个变换的行列式是 1/2,说明它将一个区域的面积缩小了一半。

如果一个变换的行列式是 0,说明它将一个区域的压缩到了一条线上,甚至是一个点上。此时任何区域的面积都变成了0。

image-20230905172434420

因此我们通过计算行列式,观察其是否为0,就能够知道这个矩阵所代表的变换是否将空间压缩到更小的维度上。(学习后面几节内容时你会知道这为什么会有用)

完整意义上的行列式是允许出现负值的。这表示变换改变了空间的走向

image-20230905172818123

那么三维变换呢?行列式的数值仍然表示空间的缩放比例(可以看作一个平行六面体的体积变化比例)。行列式为 0 则表示整个空间被压缩为一个平面或一条直线,或一个点。那么行列式的负值表示什么呢?这里需要引入一个新的方法来描述三维空间的走向——”右手定则“

image-20230905173340673

如果变换后你仍然可以用右手做出这样的手势(食指、中指、大拇指 分别指向 $\hat i,\hat j,\hat k$ )则说明三维空间的走向没变。如果你只能用左手做出这样的手势,则说明走向发生了改变,行列式为负值。

对于行列式的计算,二维下我们可以通过四边形面积计算公式表示

image-20230905173825898

而在三维下,我们直接给出公式(作者认为理解行列式所代表的意义比关注其数值计算过程更属于线性代数的本质)

image-20230905173927709

sagemath

1
2
3
4
5
6
7
# 行列式的计算
sage: A = Matrix([[1,3],[-2,0]])
sage: A.det()
6
sage: B = Matrix([[1,3,44],[8,-2,0],[7,22,56]])
sage: B.det()
6904

06 逆矩阵、列空间、秩与零空间

image-20230906105813308

这一节我们将透过线性变换来了解逆矩阵、列空间、秩和零空间的概念(不涉及计算的方法)

矩阵的用途,当我们有一个线性方程组的时候,我们可以把它们用矩阵乘以向量的形式表示

image-20230906124344200

我们知道矩阵 $A$ 表示一个线性变换。所以上述的例子,就是让我们求一个向量 $x$,它在进行特定线性变换 $A$ 后能够变为向量 $v$(或者可以理解为与向量 $v$ 重合)。

当矩阵 $A$ 的行列式不为 0 的情况下,有且仅有一个向量在变换后与 $v$ 重合,因此我们可以通过对向量 $v$ 进行逆变换(我们记作 $A^{-1}$)来找到这个向量。(举个例子如果 $A$ 表示的变换是逆时针旋转90°,那么 $A^{-1}$ 表示的变换就是顺时针旋转90°)很显然,当我们应用一个变换 $A$ 后紧跟着进行变换 $A^{-1}$,那么结果就是啥也没变(恒等变换),这就是 $A^{-1}$ 的核心性质。

image-20230906125529637

当我们通过计算机计算出了 $A^{-1}$ 后,我们可以通过对向量 $v$ 应用 $A^{-1}$ 变换来求得向量 $x$ (在任意维度下都通用,只要 $A$ 的行列式不为0)

image-20230906125720187

当 $A$ 行列式为 0 时,从几何直观上,这个变换讲空间压缩到更低的维度,此时就没有逆变换了,因为你不能使用函数将一条线”解压缩“为一个平面。

image-20230906130033260

但是,即使 $A$ 的行列式为 0,解也仍然可能存在。如果变换 $A$ 将平面压缩为一条线,而向量 $v$ 刚好和这条线共线,那么解存在。

image-20230906130253060

前面提到当 $A$ 的行列式为 0 时表示变换将压缩空间。但是显然将三维空间压成一条线是比将二维空间压成一条线要压缩的”更狠“。那么如何衡量呢?我们引入一个概念叫做 秩(rank)

当变换的结果是一条直线的时候,即一维,我们称其秩为 1

同理当变换的结果是一个平面的时候,我们称其秩为 2

因此 ”秩“ 代表着变换空间后的维数

另外,我们定义变换的所有输出向量 $Av$ 构成的集合,为 A的列空间

image-20230906131147700

因为矩阵的列告诉我们基向量变换后的位置

image-20230906131211447

因此秩表示的其实是列空间的维数,当秩与列数相等时,我们称之为 ”满秩“

对于一个满秩的变换,以为能在变换后落在原点的就是零向量本身,

而对于一个非满秩的变换,它将空间压缩到一个更低的维度上,因此会有一系列 向量在变换后成为零向量。

变换后落在原点的向量集合,称为矩阵的 ”零空间“”核“

举个例子当一个二维线性变换将一个平面被压缩为一条线,显然原平面中与这条线垂直的所有向量构成了”零空间“;

而一个三维线性变换将空间压缩到一条直线上,那么就会有一整个平面上的点落在原点(直观上想象应该是过原点且与线垂直的那个面);

image-20230906132428560

因此,我们不难得出,”零空间“的维数应该等于线性变换所在维数减去线性变换的秩

而“零空间”有什么作用呢?它能给出如下线性方程的所有解

image-20230906132649381

sagemath

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 矩阵 A
sage: A
[ 1 3]
[-2 0]

# A 的行列式
sage: A.det()
6

# A 的秩
sage: A.rank()
2

# A 的逆
sage: A^-1
[ 0 -1/2]
[ 1/3 1/6]


sage: B = Matrix([[1,1,1],[2,2,2],[3,4,5]])
sage: B
[1 1 1]
[2 2 2]
[3 4 5]
sage: B.det()
0
sage: B.rank()
2

# B 的零空间,维度为 3 - 2 = 1
sage: B.right_kernel()
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[ 1 -2 1]


sage: C = Matrix([[1,1,1],[2,2,2],[3,3,3]])
sage: C.det()
0
sage: C.rank()
1
# C 的零空间,维度为 3 - 1 = 2
sage: C.right_kernel()
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[ 1 0 -1]
[ 0 1 -1]

附注 2 非方阵

image-20230906134953744

非方阵也表示一种线性变换,我们同样可以通过观察基向量变换后的坐标来追踪这个变换。

image-20230906135548915

需要注意一下非方阵的叫法

image-20230906135635890

用上一节的语言来说,这个矩阵的列空间,是三维空间中一个过原点的二维平面。而这个矩阵也仍然是“满秩”的,因为列空间的维数与输入空间的维数相等,因此这个线性变换不会压缩空间。于是我们可以想象,这个变换就是将一个二维平面在三维空间中进行变换(例如将 xy平面 沿 x 轴旋转为 xz平面)

如果是列比行多的非方阵

image-20230906140646476

显然这是一种会对空间进行压缩的变换(可以手动给他加上一行零向量,就是一个不满秩的方阵了)


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081,也可以邮件至 643713081@qq.com

文章标题:密码学基础之线性代数Ⅰ

文章字数:5.4k

本文作者:Van1sh

发布时间:2023-09-06, 15:16:00

最后更新:2023-10-24, 09:45:24

原始链接:http://jayxv.github.io/2023/09/06/密码学基础之线性代数Ⅰ/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏