# Sequences and counting paths in graphs

Aug-Nov 2020

## Recap

• Vector space $V$ over a scalar field $F$
• $F$: real field $\mathbb{R}$ or complex field $\mathbb{C}$ in this course
• $m\times n$ matrix A represents a linear map $T:F^n\to F^m$
• dim null $T$ + dim range $T$ = dim $V$
• Linear equation: $Ax=b$
• Solution (if it exists): $u+$ null$(A)$
• Four fundamental subspaces of a matrix
• Column space, row space, null space, left null space
• Eigenvalue $\lambda$ and Eigenvector $v$: $Tv=\lambda v$
• Distinct eigenvalues have independent eigenvectors
• Basis of eigenvectors results in a diagonal matrix for $T$
• Every linear map has an upper triangular matrix representation

## Fibonacci sequence

0,1,1,2,3,5,8,13,21,

$a_k = a_{k-1}+a_{k-2}$, $a_0=0, a_1=1$

Let $x_k=(a_k,a_{k-1})$

$x_k = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}x_{k-1}$

Eigenvalues: $\dfrac{1+\sqrt{5}}{2}$, $\dfrac{1-\sqrt{5}}{2}$

Eigenvectors: $(\dfrac{1+\sqrt{5}}{2},1)$, $(\dfrac{1-\sqrt{5}}{2},1)$

$a_k=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^k-\left(\dfrac{1-\sqrt{5}}{2}\right)^k\right]$

## Binary sequences with no consecutive 1s

$a_k$ = no. of binary sequences of length $k$ with no consecutive 1s

$b_k$ = no. of binary sequences of length $k$ with no consecutive 1s ending in 0

$c_k$ = no. of binary sequences of length $k$ with no consecutive 1s ending in 1

$a_k=b_k+c_k$

$b_{k+1}=b_k+c_k$, $c_{k+1}=b_k$

$\begin{bmatrix} b_{k+1}\\ c_{k+1} \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}\begin{bmatrix} b_k\\ c_k \end{bmatrix}$

$a_k=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{k+2}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{k+2}\right]$

## Counting walks in graphs

• Previous example: count walks of length $k$ in the directed graph below

• Count walks of length $k$ in graph below