Sequences and counting paths in graphs

Andrew Thangaraj

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

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]\)

\(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]\)