Dec 3, 2011

Dynamics of Undirected Graphs

It's understandable that each undirected graph is also a two-body interaction system. Because we can take its adjacency matrix or Laplacian matrix, which is the adjacency matrix but the diagonal terms are filled with degrees, as the Hamiltonian. Let's take a look at an example, path graph P2.
Fig. 1, P2
It's adjacency matrix can be written as: \[
H=\left(
\begin{array}{c c}
0 & 1 \\
1 & 0
\end{array} \right)
\]
As a physics student, the first thing I want to do is diagonalizing the Hamiltonian and solving for eigenspectrum.

Let's do it. Obviously $H$ has two eigenvalues, $\pm 1$. The corresponding eigenvector are $(1, 1), (1, -1)$. Wait, what does it mean by a vector like $(1, -1)$? We know that $( 1, 0)$ can be used to represent the fist vertex $v_1$, and $(0, 1)$ the second, $v_2$. This is a puzzle. Especially for arbitrary undirected graph, the eigenvalues are reals. Not to mention directed graphs!

I found a nice idea from Dr. Dan Spielman's lecture [1]. He argues that these reals can be used as coordinates of the vertices. For our simplest example, vector $(1, -1)$ indicates the coordinates for $v_1, v_2$ are 1, -1. Of course we can pick two eigenvectors and therefore get two dimensional coordinates $v_1 : ( 1, 1), v_2 (1, -1)$. It can be shown below in Fig. 2. This geometric representation of graphs is called eigenvector projection.
Fig. 2, P2 in eigenvector space.

Let's play around for some slightly more complicated graphs. I'll start with a ring $C_{20}$.

Fig. 3, $C_{20}$

Instead of using adjacency matrix, Laplacian matrix is used, which is defined as: \[
L_{i j} = \left\{ \begin{array}{cc}
\text{deg}(i) \qquad i = j; \\
- a_{i, j} \qquad i \ne j;\\
\end{array} \right.
\] where $a_{i,j}$ is the entry of adjacency matrix. The Laplacian matrix of an undirected unweighted graph has the following property:
  1. It is positive defined. 
  2. It always has an eigenvector $(1, 1, \cdots 1)$, the corresponding eigenvalue is 0. 
  3. The multiplicity $p$ of eigenvalue 0, is the number of connected components of the graph. 
  4. Further more, the second second smallest eigenvalue of Laplacian matrix is called the algebraic connectivity. It is a characteristic parameter of the connectivity of the graph.
Fig. 4. Eigen-projection of $C_{20}$, use the 1st and 2nd eigenvectors. (sorted by eigenvalues)

Fig. 5, 1 - 3rd eigenvectors of $C_{20}$. (sorted by eigenvalues)

From Fig. 5, we can see harmonic modes that we are familiar with in physics. So besides the mathematical argument, we also have visualization of eigenvectors from the point of view of physics, as you expect. These eigenvalues are just the energy spectrum, with eigenvectors of the modes. The (2 dimensional) eigen-projections of a graph, therefore is the what we call Lissajous curves.

Fig. 6 Lissajous curves of various pair of modes.

The Lissajous curves of harmonics may have some aesthetic  value. Yet for discrete object like graphs, only the low energy modes generate smooth Lissajous curves. The high frequency modes are known as "fuzzy" ones.

Fig. 8 Eigen-projection of $C_{20}$ by the 2nd and 4th modes.
The eigenvector projection goes to crazy when the graphs get complicated. Several examples are presented below.
Fig. 9, A graph $C_{50}(7)$.
Fig. 12 Projection on the last two eigenvectors.

It can be shown, in the space spanned by the full eigenvectors, this projection provides an optimal graph layout under several constraints. For example, the eigenvector projection minimizes the following function:

\[
   z = \sum_{v_i, v_j \in V} A_{i,j} d^{(p)}_{i,j}
 \]
with subjected to the constraint: \[ \sum_{v_i, v_j \in V} d^{(p)}_{i,j} = 1.\], where $d^{(p)}$ is $p$ dimensional distance.

Unfortunately, it is difficult to directly visualize system in high dimensions. In 3 dimension or 2 dimension, the eigenvector projection tends to  squeeze in some directions, therefore not preferred for display small graphs.

In physics, the Hamiltonian matrix is always given in some basis, for instance quantum mechanical version of real space (Hilbert space). It is difficult to plant Hilbert space on a graph, yet nature has provided us a vector space on vertices, the tangent bundle $TG$, or the space of small vibrations, in the perspective of physics. We can take the $L^2$ space associated with this space as Hilbert space.

Therefore, the eigenvectors and eigenvalues can be seen as the modes of small vibrations of the graph instead of the actual position of graph vertices . Eigenvalues, as you wish, are just frequencies, or energies. The vibration picture allows us to make use of the full information of the eigensystem. I produced some animations of some vibrating graphs. Well, yeah, these are not so pretty... I'll try to make some better ones.

dim = 5;
lapmat = Table[If[i == j, dim - 1, -1], {i, 1, dim}, {j, 1, dim}];
MatrixForm[lapmat]

g0 = GraphPlot3D[lapmat, 
  VertexRenderingFunction -> ({Orange, Opacity[0.9], 
      Sphere[#1, .08]} &), 
  EdgeRenderingFunction -> ({ColorData["TemperatureMap", 0.2], Thick, 
      Opacity[0.7], Line[#1]} &), Method -> Automatic, 
  PlotStyle -> Directive[PointSize[0.05]], Boxed -> False, 
  ImageSize -> 400, BoxRatios -> {1, 1, 1}]

coor = VertexCoordinateRules /. Cases[g0, _Rule, Infinity];
{eval, evec} = Eigensystem[lapmat];

Manipulate[
 GraphPlot3D[lapmat, PlotStyle -> Thick, 
  VertexRenderingFunction -> ({Orange, Opacity[0.9], 
      Sphere[#1, .08]} &), 
  EdgeRenderingFunction -> ({ColorData["TemperatureMap", 0.2], Thick, 
      Opacity[0.7], Line[#1]} &), Boxed -> False,
  VertexCoordinateRules -> 
   Table[i -> (coor[[i]] + 
       amp*Sin[eval[[n]] t]*{evec[[i, x]], evec[[i, y]], 
         evec[[i, x]]}), {i, 1, dim}] , ViewPoint -> {10, 2, 0.4}, 
  BoxRatios -> {1, 1, 1}], {t, 0, 2 Pi}, {x, 1, dim, 1}, {y, 1, dim, 
  1}, {z, 1, dim, 1}, {{amp, 0.03}, 0, 0.1}, {n, 1, dim, 1}]

Fig. 15, one of the vibration modes of K4
Fig. 16, one of the vibration mode of K4
Fig. 17, one of the vibration mode of K4

Fig. 18, vibration modes of a string graph.


Update (Dec. 4, 2011):

This provides a simplest "quantum field" model. One may view the lattice graph as the timespace lattice (with respect to some basis). Of course, the discrete model has significant differences from continuous ones. Therefore, only the low energy modes can be used.

Mathematical interests on these vibrating graphs arises when these is a (finite) group, usually the symmetry group of the graph, acting on it (Consider the complete graph $K_4$. The Hilbert space we planted on the graph serves as the linear representations of the group. Therefore, certain eigenvectors may be orthogonal by group theory. In physics, the square of Hermitian inner product of vectors are proportion to transition probability. It can be observed through atomic spectra distribution and intensity. Therefore, the group representations determine the atomic spectra. This is another story behind the vibration of graphs. Although I'm in physics, I learned it from one of my math teachers, Dr. Basak Tathagata. The details are beyond my capability. E. Wigner's book is canonical on this subject.

Update (Jan. 7, 2012)
Significant change has been made. I used Laplacian matrix this time. It yields positive, well ordered eigenspectrum. Therefore, almost all graphs were updated. I still use Mathematica to generate graphs. But a software gifsicle was used to generate animations gif picture. Mirage serves as gif viewer.

Nov 9, 2011

LaTeXing in Blogger


Powered by MathJax


There are several ways to use latex in blogger. Here I present the one I believe the best, MathJax.

1. add Gadget -> JavaScript/HTML

2. do not fill in title, copy the following lines into the content part:


examples:

I. Newton: $\mathbf{F} = m\cdot\mathbf{a},  f = -\frac{G m_1 m_2}{r^2}.$

J. Maxwell: $\partial_\nu F^{\mu \nu} = \mu_0 J^\mu$; $\epsilon^{\mu \nu \sigma \rho} \partial_\nu F_{\sigma \rho} = 0$.

J. Gibbs: $ \rho \propto e^{-\beta (H - \mu N)}$.

A. Einstein: $\frac{d}{d\tau}p^\mu = f^\mu, G^{\mu \nu} = \frac{8 \pi G}{c^4} T^{\mu \nu}.$

E. Schrodinger: $ i\hbar \frac{\partial}{\partial t}\left. |\psi\right> = H \left.| \psi \right>, G_{\mu\nu} = \frac{ 8 \pi G }{ c^4 } \left\langle \hat T_{\mu\nu} \right\rangle_\psi$

R. Feynman: \[
D_F(x - x') = \int \mathcal{D}\varphi \; \exp \left\{ \frac{i}{\hbar} S[\varphi] \right\}.
\]

J. Schwinger: \[
\left\{
\frac{\delta}{\delta \varphi(x)} S\left[ \frac{1}{i}\frac{\delta}{\delta J} \right] + J(x) \right\} \int \mathcal{D}\varphi \; \exp\left( \frac{i}{\hbar}S[\varphi, J] \right) = 0.
\]

Jun 6, 2011

Textbooks on Quantum Field Theory

Introductory and Intermediate:

Berestetskii, V. B.; Lifshitz, E.M.; Pitaevskii, L.P. (1982). (2nd ed.), (Vol. 4). Quantum Electrodynamics.
Ryder, L.H. (1985). Quantum Field Theory.
Coleman, Sidney (1988). Aspects of Symmetry.
Mandl, F.; Shaw, G. (1993). Quantum Field Theory.
Greiner, W.; Reinhardt, J. (1994). Quantum Electrodynamics.
Lowell S. Brown (1994). Quantum Field Theory.
Peskin, M.; Schroeder, D. (1995). An Introduction to Quantum Field Theory.
Greiner, W.; Müller, B. (2000). (3rd ed.). Gauge Theory of Weak Interactions.
Mahan, G. D. (2000). (3rd ed.). Many-Particle Physics.
Zee, A (徐一鸿). (2003). Quantum Field Theory in a Nutshell.
Clarkson, R.; McKeon, D. G. C. (2003). Quantum Field Theory.
Nair, V. (2004). Quantum Field Theory: a modern perspective.
李政道 (2006). 粒子物理和场论.
Srednicki, Mark (2007). Quantum Field Theory.
Alexander, A.; Simon, B. (2007). Condensed Matter Field Theory.
Reinhardt, J.; Greiner W. (2008). Field Quantization.
McMahon, David (2008). Quantum Field Theory Demystified.
Das, A. (2008). Lectures on quantum field theory.
Banks, Tom (2008). Modern Quantum Field Theory: A Concise Introduction.
Dimock, Jonathan (2011). Quantum Mechanics and Quantum Field Theory: A Mathematical Primer.
Kleinert, H. (book in preparation). Particle and Quantum Fields.

Advanced:

Bogolubov, N. N.; Logunov, A. A.; and Todorov, I. T.. (1975). Introduction to Axiomatic Quantum Field Theory.
Abrikosov, A. A. (1975). Methods of Quantum Field Theory in Statistical Physics.
Itzykson, C.; Zuber, J.-B. (1980). Quantum Field Theory.
Collins, John (1986). Renormalization: An Introduction to Renormalization, the Renormalization Group and the Operator-Product Expansion.
Fradkin, E. (1991). Field Theories of Condensed Matter System.
Weinberg, S. (1995). The Quantum Theory of Fields, Vol. I, II, III.
Shifman, M. (2012). Advanced Topics in Quantum Field Theory: a lecture course.

Special Topics:

DeWitt, B. (1975). Quantum Field Theory in Curved Spacetime.
Wald, Robert M. (1994). Quantum Field Theory in Curved Spacetime and Black Hole Thermodynamics.
Quigg, Chris (1997). Gauge Theories of the Strong, Weak, and Electromagnetic Interactions.
Kleinert, H.; Schulte-Frohlinde, Verena (2001). Critical Properties of $\varphi^4$-Theories.
Zinn-Justin, Jean (2002). Quantum Field Theory and Critical Phenomena.
Connes, A; Marcolli, M. (2007). Noncommutative Geometry, Quantum Fields and Motives.

Lecture Notes:

Siegel, W. (1999). Fields.
Etingof, Pavel. Mathematical ideas and notions of quantum field theory.
Dolgachev, Igor V.. Quantum Field Theories: an introduction.
Borcherds, R. E.; Barnard, A.. Lectures on Quantum Field Theory.
Segal, Irving. Introduction to Algebraic and Constructive Quantum Field Theory.
Tong, David, Quantum Field Theory.
Mulders, P. J.. Quantum Field Theory.
Polyak, Michael (2004). Feynman diagrams for pedestrians and mathematicians.
Casalbuoni, Roberto (2005). Advanced Quantum Field Theory.
Schmidt, Michael G. (2007). Quantum Field Theory I.
Arodz, Henryk; Hadasz, Leszek (2011). Lectures on Classical and Quantum Theory of Fields.
Luke, M. (2011). PHY2403F Lecture Notes.
Flory, Mario; Helling, Robert C.; Sluka, Constantin (2012). How I Learned to Stop Worrying and Love QFT.
Osborn, Hugh (2013). Advanced Quantum Field Theory.
Fredenhagen, Klaus; Rejzner, Katarzyna (2013). Perturbative algebraic quantum field theory.

Legacy Lecture Notes:

Fermi, E. (1932). Quantum Theory of Radiation.
http://fafnir.phyast.pitt.edu/py3765/FermiQED.pdf

Dyson, Freeman (1951). Quatum Field Theory notes at Cornell.
http://fafnir.phyast.pitt.edu/py3765/DysonQFT.pdf

Coleman, Sidney (1985). Quatum Field Theory notes at Harvard.
http://fafnir.phyast.pitt.edu/py3765/Coleman-QFT.pdf