Markov Matrix

A $n\times n$ matrix whose elements are non-negative and every column vector sums to $1$ is known as Markov Matrix(a.k.a. stochastic matrix).
Say

$$A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix}$$

So,

• $a_{ij}\geq 0;\quad\forall i,j\in\{1,2,\cdots,n\}$
• $\sum_{i=0}^{n}a_{ij}=1\quad\forall j\in\{1,2,\cdots,n\}$

$\lambda_1=1$

info

Markov matrix always have one of the eigenvalues $=1$.

note

Proof:

$$A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix}$$

$$A-1\mathcal{I}=\begin{bmatrix} a_{11}-1 & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22}-1 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn}-1 \\ \end{bmatrix}$$

Now we apply $R_n \leftarrow R_1 + R_2 + \cdots + R_n$

$$A-\mathcal{I}=\begin{bmatrix} a_{11}-1 & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22}-1 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \sum_{i=0}^{n}a_{i1} -1 & \sum_{i=0}^{n}a_{i2} -1 & \cdots & \sum_{i=0}^{n}a_{in} -1 \\ \end{bmatrix}$$

And as we know that $\sum_{i=0}^{n}a_{ij}=1\quad\forall j\in\{1,2,\cdots,n\}$

$$A-\mathcal{I}=\begin{bmatrix} a_{11}-1 & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22}-1 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \\ \end{bmatrix}$$

So now we can see that $\text{det}(A-\mathcal{I})=0$
So indeed $\lambda=1$.

Example of Markov Matrices

Assume that we have two cities $A$ and $B$ and at the end of the year we calculate the

• Proportion of peoples remains in city $A$, we denote it by $p_{a}$
• Proportion of peoples remains in city $B$, we denote it by $p_{b}$
• Proportion of peoples moved from city $A$ to $B$, we denote it by $p_{ab}$
• Proportion of peoples moved from city $B$ to $A$, we denote it by $p_{ba}$

We can represent this information as a Markov Matrix (say $M$).

$$\begin{matrix} & \text{Moved to } A & \text{Moved to } B \\ \text{From } A & p_{a} & p_{ba}\\ \text{From } B & p_{ab} & p_{b}\\ \end{matrix}$$

$$M=\begin{bmatrix} p_{a} & p_{ba}\\ p_{ab} & p_{b}\\ \end{bmatrix}$$

$p_a + p_{ab}=1$ (here we took all peoples in city $A$)
$p_b + p_{ba}=1$ (here we took all peoples in city $B$)
And proportions are positive and cannot be greater then $1$
So it is a Markov Matrix

Now say that at time $t=k$.

• Number of peoples in city $A$ are $u_A$
• Number of peoples in city $B$ are $u_B$ So at that at time $t=k+1$ we can say,

$$\begin{bmatrix} u_{A}\\u_{B}\\ \end{bmatrix}_{t=k+1}=\begin{bmatrix} p_{a} & p_{ba}\\ p_{ab} & p_{b}\\ \end{bmatrix}\begin{bmatrix} u_{A}\\u_{B}\\ \end{bmatrix}_{t=k}$$

Say that we know $u_{t=0}$ and we want to find $u_{t=100}$ then we have to compute $M^{100}$ but for large $M$ it's impractical to compute.
Now say that eigenvalues of $M$ is $\lambda_1$ and $\lambda_2$ and eigenvectos of $M$ is $x_1$ and $x_2$
So,

danger

$$\begin{matrix} \displaystyle \vec{u}_{t=k}=c_1\lambda_1^k\vec{u}_{t=0} + c_2\lambda_2^k\vec{u}_{t=0} \end{matrix}$$

Expansion with Orthogonal basis

Say that we are in $n$ dimensional space and $\vec{q}_1, \vec{q}_2, \cdots, \vec{q}_n$ are the basis for that $n$ dimensional space.
Here all $\vec{q}_1, \vec{q}_2, \cdots, \vec{q}_n$ are orthogonal
We can express any vector in this $n$ dimensional space as the linear combination of basis vectors.
Assume a vector $\vec{v}\in\mathbb{R}^n$ in this $n$ dimensional space.
we can express $\vec{v}$ as,
$\vec{v}=x_1\vec{q}_1 + x_2\vec{q}_2 + \cdots + x_n\vec{q}_n$
Ok we can express $\vec{v}$ as linear combination of basis vectors but we are interested in these $x_1, x_2, \cdots, x_n$.

How can we compute $x_1, x_2, \cdots, x_n$?
First let's see how can we get $x_1$?
IDEA: All $\vec{q}_1, \vec{q}_2, \cdots, \vec{q}_n$ are orthogonal so $\vec{q}_i^T\vec{q}_j=0;\quad \forall i\neq j$
so take dot product w.r.t. $x_1$.

$\vec{v}^T\vec{q}_1=x_1\underbrace{\vec{q}_1^T\vec{q}_1}_{=1} + x_2\underbrace{\vec{q}_2^T\vec{q}_1}_{=0} + \cdots + x_n\underbrace{\vec{q}_n^T\vec{q}_1}_{=0}$

$\Rightarrow x_1=\vec{v}^T\vec{q}_1$

danger

$$\begin{matrix} \displaystyle x_i=\vec{v}^T\vec{q}_i;\quad\forall i\in\{1,2,\cdots, n\} \end{matrix}$$

Say

$$\begin{bmatrix} \vdots & \vdots & & \vdots \\ \vec{q}_{1} & \vec{q}_{2} & \cdots & \vec{q}_{n} \\ \vdots & \vdots & & \vdots \\ \end{bmatrix}=Q \text{ and } \vec{x}=\begin{bmatrix} x_1\\ \vdots \\x_n\\ \end{bmatrix}$$

We can also write it in matrix form,

$$\begin{bmatrix} \vdots & \vdots & & \vdots \\ \vec{q}_{1} & \vec{q}_{2} & \cdots & \vec{q}_{n} \\ \vdots & \vdots & & \vdots \\ \end{bmatrix} \begin{bmatrix} x_1\\ \vdots \\x_n\\ \end{bmatrix} = \vec{v}$$

$\Rightarrow Q\vec{x}=\vec{v}$
$\Rightarrow \underbrace{Q^TQ}_{\mathcal{I}}\vec{x}=Q^T\vec{v}$

danger

$$\begin{matrix} \displaystyle \vec{x}=Q^T\vec{v} \end{matrix}$$

Fourier Series

$$f(x)=a_0 1+a_1\cos(x)+b_1\sin(x)+a_2\cos(2x)+b_2\sin(2x)+\cdots$$

Here instead of vectors we are using functions, so here we are computing linear combinations of functions (instead of vectors).
Here our space is $\infty$ dimensional

• In vector case dot product is like,

  Say $\vec{v}= \begin{bmatrix} v_1\\ \vdots \\v_n\\ \end{bmatrix}$ and $\vec{u}= \begin{bmatrix} u_1\\ \vdots \\u_n\\ \end{bmatrix}$
  $\vec{v}\cdot\vec{u}=v_1u_1 + v_2u_2 + \cdots + v_1u_n$

• For function dot product is like,

  Vectors have some set of values like $\vec{v}= \begin{bmatrix} v_1\\ \vdots \\v_n\\ \end{bmatrix}$.
  But a function has a range of values like for $\cos(x)$ range is $[0,2\pi]$.
  And a dot product of two functions say $f$ and $g$ with interval $[0,2\pi]$ is defined as.

danger

$$\begin{matrix} f\cdot g=\int_{0}^{2\pi}f(x)g(x)dx \end{matrix}$$

Here our functions are $1,\cos(x),\sin(x),\cos(2x),\sin(2x),\cdots$
$\cos$ and $\sin$ are periodic function with period of $[0,2\pi]$, so $0\leq x\leq 2\pi$
So we have $\infty$ orthogonal basis.
Now we want to find $a_0,a_1,b_1,a_2,b_2,\cdots$
First let's see how to find $a_1$?

$$f(x)=a_0 1+a_1\cos(x)+b_1\sin(x)+a_2\cos(2x)+b_2\sin(2x)+\cdots$$

IDEA: take dot product with function with $a_1$

$$f(x)\cdot\cos(x) =a_0 1\cdot\cos(x) +a_1\cos(x)\cdot\cos(x) +b_1\sin(x)\cdot\cos(x) +a_2\cos(2x)\cdot\cos(x) +b_2\sin(2x)\cdot\cos(x) +\cdots \\ \quad \\ \Rightarrow \int_{0}^{2\pi}f(x)\cos(x) =\underbrace{\int_{0}^{2\pi}a_0 1\cos(x)}_{=0} + \int_{0}^{2\pi}a_1\cos(x)\cos(x) + \underbrace{\int_{0}^{2\pi}b_1\sin(x)\cos(x)}_{=0} + \underbrace{\int_{0}^{2\pi}a_2\cos(2x)\cos(x)}_{=0} + \underbrace{\int_{0}^{2\pi}b_2\sin(2x)\cos(x)}_{=0} +\cdots \\$$

$$\Rightarrow \int_{0}^{2\pi}f(x)\cos(x) =\int_{0}^{2\pi}a_1\cos(x)\cos(x) \\ \Rightarrow \int_{0}^{2\pi}f(x)\cos(x) =a_1\pi \\ \Rightarrow \int_{0}^{2\pi}f(x)\cos(x) =a_1\pi \\$$

So,

danger

$$\begin{matrix} a_1=\frac{1}{\pi}\int_{0}^{2\pi}f(x)\cos(x) \end{matrix}$$

Similarly we can find rest of $a_i$'s