简单记录一下今天面试问到的问题以及正确答案。基本上全是在问Linear Algebra的各种问题。不过有一点我没有想到的是，他们居然会让我讲我的论文以及CTF比赛的内容。（当然，论文的部分跟我预想的一样，他们应该只听懂了introduction的部分。毕竟这东西实在是太纯数了点，基本上没有任何实际应用。）
1. 怎么样可以快速确定一个矩阵的秩（rank）？（假设$A \in \mathbb{R}^{m \times n}$）
高斯消元法（Gauss Elimination）
- 秩为非零行的数量
- 不够稳定，因为会做除法。但如果只希望求秩的话则不需要考虑这个问题。
- 复杂度：$\mathcal{O}(n^3)$
QR分解（QR Decomposition）：
$Q \in \mathbb{R}^{m \times m}$是正交（orthogonal）矩阵，$R \in \mathbb{R}^{m \times n}$是上三角矩阵。
秩为R的非零对角元素个数（non-zero diagonal entries）
相对稳定
复杂度：$\mathcal{O}(n^3)$
SVD分解（SVD Decomposition）：
$U \in \mathbb{R}^{m \times m}$是列正交矩阵（左奇异向量），$V \in \mathbb{R}^{n \times n}$是列正交矩阵（右奇异向量），$\Sigma \in \mathbb{R}^{m \times n}$是对角矩阵，对角线元素是非负实数，为奇异值（Singular Values）。
秩为非零奇异值的个数
非常稳定。
复杂度：$\mathcal{O}(n^3)$
注意，他们的理论复杂度是一样的，但是常数项是不同的，所以在实际应用中，高斯是最快的，其次是QR分解，最后才是SVD分解。
2. 将这个问题建模并解决它：假设现在有n个物品（有不同的大小），并且有很多种不同大小的盒子，每个盒子里，只要大小允许，就可以放多个物品。我们希望minimize最后的盒子的数量以及多余的空间。
不会。
3. 一个矩阵在什么情况下会不存在特征值？
对于实数矩阵来说，当它的characteristic function在$\mathbb{R}$上没有根，那么它就没有特征值。比如说
characteristic function：
而对于复数矩阵来说，它们永远都会有特征值，因为$\mathbb{C}$是complete的，所以它的characteristic function在$\mathbb{C}$一定有根。
他们还问了一个least square相关的，但我从来没有听过那个词。我记得是least square前面跟了一个什么单词，但我没查到是什么。
