\( \newcommand\al{\alpha} \newcommand\be{\beta} \newcommand\de{\delta} \newcommand\De{\Delta} \newcommand\eps{\epsilon} \newcommand\ga{\gamma} \newcommand\Ga{\Gamma} \newcommand\ka{\kappa} \newcommand\la{\lambda} \newcommand\La{\Lambda} \newcommand\om{\omega} \newcommand\Om{\Omega} \newcommand\sg{\sigma} \newcommand\Sg{\Sigma} \renewcommand\th{\theta} %--- Latex uses \th for a Norse character \newcommand\Th{\Theta} \newcommand\vphi{\varphi} % % some calligraphy % \newcommand\cA{{\mathcal A}} \newcommand\cB{{\mathcal B}} \newcommand\cC{{\mathcal C}} \newcommand\cD{{\mathcal D}} \newcommand\cE{{\mathcal E}} \newcommand\cF{{\mathcal F}} \newcommand\cG{{\mathcal G}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cJ{{\mathcal J}} \newcommand\cK{{\mathcal K}} \newcommand\cL{{\mathcal L}} \newcommand\cM{{\mathcal M}} \newcommand\cN{{\mathcal N}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\cQ{{\mathcal Q}} \newcommand\cR{{\mathcal R}} \newcommand\cS{{\mathcal S}} \newcommand\cT{{\mathcal T}} \newcommand\cU{{\mathcal U}} \newcommand\cV{{\mathcal V}} % % fields and rings (and a semigroup) % \newcommand\cx{{\mathbb C}}% complexes \newcommand\fld{{\mathbb F}} \newcommand\flde{{\mathbb E}} \newcommand\ints{{\mathbb Z}} \newcommand\nn{{\mathbb N}}%non-negative integers \newcommand\re{{\mathbb R}}%reals \newcommand\rats{{\mathbb Q}} % % the really useful stuff % \newcommand\comp[1]{{\mkern2mu\overline{\mkern-2mu#1}}} \newcommand\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus \newcommand\res{\mathbin{\mkern-2.0mu\restriction\mkern-2.0mu}} \newcommand\sbs{\subseteq} \newcommand\sps{\supseteq} \newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\row}{row} \newcommand\pmat[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand\cprod{\mathbin{\square}} \newcommand\gbin[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % % matrix theory % \newcommand\ip[2]{\langle#1,#2\rangle} \newcommand\one{{\bf1}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\col}{col} \newcommand\mat[3]{\mathrm{Mat}_{#1\times #2}(#3)} \newcommand\sm[3]{\sum_{#1=#2}^{#3}} % % some group theory % \newcommand\aut[1]{{\rm Aut}(#1)} \newcommand\fx[1]{{\rm fix}(#1)}% ch2 \newcommand\grp[1]{\langle #1\rangle} \newcommand\nrml{\vartriangleleft} \newcommand\nrmleq{\trianglelefteq} \DeclareMathOperator{\Sym}{Sym} \newcommand\sym[1]{\Sym(#1)} \DeclareMathOperator{\Alt}{Alt} \newcommand\alt[1]{\Alt(#1)} \)

Section7.1Continuous Quantum Walks

One goal of this section is to introduce you to the joys of numerical linear algebra with Sage.

Suppose \(A\) is the adjacency matrix of \(X\). We define \(H(t)=H_X(t)\) by

\[H =\exp(iAt)\]
We are concerned with the absolute values of the entries \(H(t)\), and in particular want to know when we can have
\[|H(\tau)_{u,v}| =1\]
for some time \(\tau\) and some vertices \(u\) and \(v\). Since \(A\) is symmetric it has a spectral decomposition
\[A =\sum_\th \th E_\th\]
and consequently
\[H(t) = \sum_\th \exp(i\th t)E_\th\]

To use this formula we need an orthogonal basis for each eigenspace. The difficulty if that if we work in floating point, then we have to decide which eigenvalues are actually equal before we determine an eigenspace.

We are going to use scipy and numpy. It seems that numpy is basically an array package, which provides such things as \(k\)-dimensional arrays. (Computer scientists seem to think these are useful, I have no idea why.) Scipy builds on numpy, providing access to standard linear algebra routines (eigenthings, svd, etc.) There is on-line documentation for scipy and numpy, but it is not very good. (For example it illustrates how to solve linear equations by inverting the matrix of coefficients.) The syntax for scipy and numpy is not consistent with Sage, or with python.

Anyway, here is the opening incantation:

We will go through some simple computations, so you can get a feel for things.

Now with

we get the eigenvalues of \(AP\) (in \(\la\)) and the eigenvectors (in \(v\)). The routine linalg.eigh takes a Hermitian matrix and returns real eigenvalues. Eigenvectors corresponding to distinct eigenvalues are orthogonal. Note that the eigenvectors are returned by linalg.eigh as numpy arrays, and there is a argument for wrapping it in a routine that immediately transforms them into Sage vectors.

We intend to make use of the fact that if the vectors \(\seq z1m\) are an orthogonal basis for a subspace then the matrix representing projection onto the subspace is

\[z_1z_1^T+\cdots+z_mz_m^T\]
The problem is that our eigenvalues have been computed in floating point, and so we need a routine with arguments \(\la\) and \(\eps\) which divides the eigenvalues into equivalence classes, where two eigenvalues are equivalent if their difference is less than \(\eps\). The output of the routine is a dictionary keyed on distinct eigenvalues and the entry with given eigenvalue is the set of indices of the eigenvalues equivalent to the key.

Given this it is straightforward to write the code that takes this dictionary and returns a list of pairs consisting of an eigenvalue and its associated projection.