​ Firstly, we consider a large data matrix $X\in \mathbb{C}^{n\times m}$:

The column $x_k\in \mathbb{C}^n$ is obtained from simulations or experiments. Here,we always consider the column vectors may also represent the state of a physical system that is evolving in time.The column are often called snapshots and $m$ is the number of snapshots in $X$.

The Singular Value Decomposition allows us to decompose any complex-valued matrix as the product of three other matrices,

文件目录管理

下表罗列了Linux文件系统中主要目录的内容

Shell 基本命令

Bash提供了命令行补全的特性.我们可以利用Tab键来完成命令以及文件名的自动补全.如果以已输入的字符开头的文件不止一个,那么连续输入两次Tab键,shell将会以列表的形式给出所有以输入字符开头的文件名.

同样我们可以补全Linux命令,这是因为Linux的命令本质上是一些可执行文件,所以可以认为命令补全和文件名补全其实是同一件事.

此外,Shell在查找文件中存在通配符的专用符号,其为*,?,[].这些通配符可以搜索并匹配文件名的一部分,从而可以做到批量检索文件.

Proof of the coloring-flow duality theorem

Thm(Wilf,1967) Let G be a graph. Then $\chi(G)\leq\lambda_1(G)+1$, where $\chi(G)$ is the chromatic number

A proper vertex coloring is a map $c:V(G)\to\mathbb{N}$ s.t. $c(v_i)\not=c(v_j)$ if $v_iv_j\in E(G)$.

A graph is a k-colorable if there exists a proper vertex coloring

Interlacing Theorem

Thm(Eigenvalue Interlacing Theorem)
Let A be a symmetric real $n\times n$ and let B be an m-th principal submatrix(obtained by deleting both i-th row and i-th column for some n-m values of i). Suppose A has eigenvalues $\lambda_1\geq\cdots\geq\lambda_n$, and B has eigenvalues $\beta_1\geq\cdots\geq\beta_m$.Then

Let G be a finite graph. We consider a random walk on the vertices of G of the following type. Start at a vertex $v$ .(v could be chosen randomly according to some probably distribution or could be specified in advance). Among all edges incident to v, choose one uniformly at random( i.e. if $d_G(v)=d$, each of these edges is chosen with probability 1/d)

Problem: determine the probability of being at a given vertex after a given number steps.

Proposition. The adjacency matrix of a graph is a real symmetric matrix.

Given a graph G, $T={v|d_G(v)\equiv1\ mod\ 2}$, a subgraph P is called a parity subgraph if

$G-E(P)$ is an even subgraph ( i.e. every vertex of G-E(P) has even degree)
Problem: To find a parity subgraph with the minimum number of edges.

First, we try to prove the Mantel’s Theorem, which was presented as a question in the last blog post.

Thm(Mantel’s Theorem)
Let G be a graph with n vertices. If G does not contain a triangle, then

Before the proof begin, we introduce what triangle means.