Math

没事瞎水博客系列……

在日常处理矩阵的时候，有时我们希望在不更改矩阵的前提下获知其每一行/列的字典序“名次”（rank）。MATLAB/NumPy分别提供了sortrows/argsort方法来获得一个“索引向量”（index vector），表示排序后的矩阵的每一行/列对应原矩阵的行/列号。只需对索引向量再做一次排序，便可得到对应的”名次向量“（rank vector）。对应MATLAB代码大致如下：

[~, index] = sortrows(matrix);
[~, rank] = sort(index);

为了深入理解这个操作背后的原理，我参考了StackExchange上的这篇回答。从他的证明过程中我发现了一个关键：排序前后两个矩阵的关系可以用排列/置换（permutation）来刻画。下面我将站在线性代数的视角来系统化解释一下“名次向量”背后的原理。

龟速补上欠下的账ing……

写完发现读着好晦涩，但数学不就是这样的吗🌚

基本概念/符号表示

为了方便下文叙述，现做如下规定/定义：

$G = (V, E)$是有向、无平行边的图，每条边边权为正，其中有一个源点（source）$s$和汇点（sink）$t$满足：没有一条边以$t$为起点，或以$s$为终点。

对某边$e \in E$，记该边边权为$c(e)$。

写在前面

本文仅面向学习FFT算法的CS学生。文中关于傅里叶变换的阐述仅用于帮助快速简要地理解算法背后时域/频域变换的意义，逻辑性不会像「信号与系统」课那么强。本人没系统学过「信号与系统」这门课，能写出这篇文章也要感谢来自FDU、SCUT的两位同学的帮助。欢迎各位大佬对本文内容进行指正！

要系统学习「信号与系统」的内容，可参阅奥本海默著的《信号与系统》一书。

在我学习FFT时，第一个面对的问题背景是「给定两个多项式，如何快速求得二者的乘积？」老师或者博客会先介绍多项式的系数表示和点值表示（在下一节也会再啰嗦一遍），然后引入单位根和分治思想来实现两种表示法间的转换。这篇专栏对算法内容及前置知识的讲解算是非常详尽的了，但它并没有解决一个问题：傅里叶变换的本质是将时域上的卷积转化成频域上的乘法，那么多项式的系数/点值表示为什么能和信号的时域/频域对应？本文将尝试从FFT的应用意义出发来探讨这个算法，并尝试揭示其中的关联。

定义

一个整数$x$对另一个整数$p$的二次剩余，指$x^2$模$p$的余数。

我们称整数$d$为模$p$的二次剩余当且仅当$\exists x \in \mathbb{Z} \text{ s.t. } x^2 \equiv d \pmod p$；反之，称$d$为模$p$的非二次剩余。

上下文无歧义的情况下可以简称为剩余和非剩余。

置换

置换即$[\![1, n]\!] \triangleq \{1, 2, \dots, n\}$到自身的1-1变换：$[\![1, n]\!] \rightarrow [\![1, n]\!]$

$p: i \rightarrow a_i, (a_i \neq a_j, i \neq j)$，

其中$a_1, a_2, \dots, a_n$是$[\![1, n]\!]$的一个全排列，

称此置换为$n$阶置换，记为：

$$ p = \left( \begin{matrix} 1 & 2 & \cdots & n \\ a_1 & a_2 & \cdots & a_n \end{matrix} \right) $$

$n$阶置换共有$n!$个。

中国剩余定理可用于解一元线性方程组： $$ \begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2}\\ \quad \vdots\\ x \equiv a_n \pmod {m_n} \end{cases} $$