Published on

Note on Spectral Graph Theory - Lecture 1

Lecture link

Spectral graph theory lies at the intersection of linear algebra and graph theory.

Vector Spaces and Linear Transformations

Some prerequisites from linear algebra.

Linear transformations

A linear transformation T:U→VT: U \rightarrow V is a function between two vector spaces such that T(au⃗+bv⃗)=aT(u⃗)+bT(v⃗)T(a \vec{u} + b \vec{v}) = a T(\vec{u}) + b T(\vec{v})

Matrix representation

A linear transformation is completely characterized by its action on a basis. Given:

  • Basis {u⃗1,…,u⃗n}\{\vec{u}_1, \ldots, \vec{u}_n\} of UU
  • Basis {v⃗1,…,v⃗m}\{\vec{v}_1, \ldots, \vec{v}_m\} of VV
  • T(u⃗i)=a1iv⃗1+a2iv⃗2+⋯+amiv⃗mT(\vec{u}_i) = a_{1i}\vec{v}_1 + a_{2i}\vec{v}_2 + \cdots + a_{mi}\vec{v}_m for i∈[n]i \in [n]

Then TT can be represented by the coordinate matrix:

M=(a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮am1am2⋯amn)M = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}

where each column consists of the coordinates (coefficients) of T(u⃗i)T(\vec{u}_i) with respect to {v⃗1,…,v⃗m}\{\vec{v}_1, \ldots, \vec{v}_m\}.

Important: The matrix MM is defined with respect to the chosen bases of UU and VV.

For any w⃗∈U\vec{w} \in U, let x⃗\vec{x} be the coordinate vector of w⃗\vec{w} with respect to the basis {u⃗1,…,u⃗n}\{\vec{u}_1, \ldots, \vec{u}_n\}, then

Mx⃗=y⃗\begin{equation*} M\vec{x} = \vec{y} \end{equation*}

where y⃗\vec{y} consists of the coordinates of T(w⃗)T(\vec{w}) with respect to the basis {v⃗1,…,v⃗m}\{\vec{v}_1, \ldots, \vec{v}_m\} of VV. This can be easily verify.

Special case: Standard basis

When the bases are e⃗i\vec{e}_i's, the coordinates reduce to the actual vectors themselves:

M=[T(u⃗1)T(u⃗2)⋯T(u⃗n)]M = \begin{bmatrix} T(\vec{u}_1) & T(\vec{u}_2) & \cdots & T(\vec{u}_n) \end{bmatrix}

Further, observe that for any vector w⃗∈U\vec{w} \in U, Mw⃗=T(w⃗)M\vec{w} = T(\vec{w}).