Algebraic Combinatorics
by djmathman, Dec 28, 2015, 2:01 AM
aka a way to use algebra to mask the fact that actual combo is hard
I haven't done a true math post in a while, so here goes....
Chapter 1 Key Idea: Let
be a finite graph on 
vertices (not necessarily simple), and let 
denote its adjacency matrix. Then the number of closed walks on of length 
is ![\[f_G(\ell)=\sum_{i=1}^n(A(G)^\ell)_{i,i}=\operatorname{tr}\left(A(G)^\ell\right)=\lambda_1^\ell+\lambda_2^\ell+\cdots+\lambda_n^\ell,\]](//latex.artofproblemsolving.com/6/0/9/609bcc4e4fdcc62bdca9c7de8ce776ad99658610.png)
where 
is the sequence of eigenvalues of . (Note that all the 
are real by the Spectral Theorem.)
This isn't too hard to prove (and is probably made easier based on the wording of the statement). Now on to the problems I guess?
I haven't done a true math post in a while, so here goes....
Chapter 1 Key Idea: Let
be a finite graph on 
vertices (not necessarily simple), and let 
denote its adjacency matrix. Then the number of closed walks on of length 
is ![\[f_G(\ell)=\sum_{i=1}^n(A(G)^\ell)_{i,i}=\operatorname{tr}\left(A(G)^\ell\right)=\lambda_1^\ell+\lambda_2^\ell+\cdots+\lambda_n^\ell,\]](http://latex.artofproblemsolving.com/6/0/9/609bcc4e4fdcc62bdca9c7de8ce776ad99658610.png)
where 
is the sequence of eigenvalues of . (Note that all the 
are real by the Spectral Theorem.)This isn't too hard to prove (and is probably made easier based on the wording of the statement). Now on to the problems I guess?
Stanley Chapter 1 Exercise 2 wrote:
Suppose that the graph has 
vertices and that the number of closed walks of length in is ![\[8^\ell+2\cdot 3^\ell+3\cdot(-1)^\ell+(-6)^\ell+5\]](//latex.artofproblemsolving.com/8/7/b/87be345b574f9b30a4b84d9aa63d27843f6c0fe4.png)
for all 
. Let 
be the graph obtained from by adding a loop at each vertex (in addition to whatever loops are already there). How many closed walks of length are there in ?
has 
vertices and that the number of closed walks of length in is ![\[8^\ell+2\cdot 3^\ell+3\cdot(-1)^\ell+(-6)^\ell+5\]](http://latex.artofproblemsolving.com/8/7/b/87be345b574f9b30a4b84d9aa63d27843f6c0fe4.png)
for all 
. Let 
be the graph obtained from by adding a loop at each vertex (in addition to whatever loops are already there). How many closed walks of length are there in ?
,
,
and 
,
are nonzero complex numbers such that for all positive integers ![\[\alpha_1^\ell+\cdots+\alpha_r^\ell=\beta_1^\ell+\cdots+\beta_s^\ell.\]](http://latex.artofproblemsolving.com/4/c/3/4c33b8a747861a5d3e9a6bc347ce5d1f3c5cbe05.png)
Then 
and the 
'
'
be a complex number whose modulus is close to 
.
and sum on all ![\[\dfrac{\alpha_1x}{1-\alpha_1x}+\cdots+\dfrac{\alpha_rx}{1-\alpha_rx}=\dfrac{\beta_1x}{1-\beta_1x}+\cdots+\dfrac{\beta_sx}{1-\beta_sx}.\]](http://latex.artofproblemsolving.com/f/3/e/f3e4360f0965b0fe5786b24b9d40ed62160fdf3a.png)
This is an identity valid for complex numbers of sufficiently small modulus. By clearing denominators we obtain a polynomial identity. But if two polynomials in 
.
and let 
.
'
,
'
added to each diagonal entry. Thus 
,
,
,
,
,
,
,
,
,![\[\boxed{9+2\cdot 4^\ell+5\cdot 2^\ell+(-5)^\ell+3}.\]](http://latex.artofproblemsolving.com/b/b/8/bb8fdea23059941b3e6066b6126419483f063c2c.png)
Stanley Chapter 1 Exercise 3 wrote:
A bipartite graph with vertex bipartition 
is a graph whose vertex set is the disjoint union 
of 
and 
such that every edge of is incident to one vertex in and one vertex in . Show that the nonzero eigenvalues of come in pairs 
. Equivalently, prove that the characteristic polynomial of has the form 
if has an even number of vertices or 
if has an odd number of vertices for some polynomial .
with vertex bipartition 
is a graph whose vertex set is the disjoint union 
of 
and 
such that every edge of is incident to one vertex in and one vertex in . Show that the nonzero eigenvalues of come in pairs 
. Equivalently, prove that the characteristic polynomial of has the form 
if has an even number of vertices or 
if has an odd number of vertices for some polynomial .
,
,
,
,
,
and 
for all 
and 
.
,
are the eigenvalues of ![\[\lambda_1^\ell+\cdots+\lambda_n^\ell=0\qquad\text{for all odd }\ell.\]](http://latex.artofproblemsolving.com/c/2/c/c2c5452fd125900aa0a84fc2f443fbb4a69c845f.png)
Now for each positive integer 
,
denote the sum of the 
powers of the eigenvalues and 
denote their 
for all odd 
,
for all 
,![\[P_{i+2}-S_1P_{i+1}+S_2P_i-\cdots+S_{i+1}P_1-(i+2)S_{i+2}=0.\]](http://latex.artofproblemsolving.com/2/9/f/29f42f9817ef9878fd502ca24ef93d409327778b.png)
Consider the expression 
for some arbitrary 
must be odd. If 
from the original problem statement. Thus 
for each ![\[-(i+2)S_{i+2}=0\quad\implies\quad S_{i+2}=0.\]](http://latex.artofproblemsolving.com/c/8/9/c897dafac635345bc800083a4af190a6db8692ad.png)
Hence we're done by induction. ![\[\lambda(A(G))=\sum_{i=0}^na_i\lambda^i\]](http://latex.artofproblemsolving.com/a/a/7/aa7230c08ed6dfc75a56213023056da7587fad3c.png)
be the characteristic polynomial of 
.
,![\[\lambda(A(G))=\begin{cases}a_n\lambda^n+a_{n-2}\lambda^{n-2}+\cdots+a_0,&n\text{ even},\\a_n\lambda^n+a_{n-2}\lambda^{n-2}+\cdots+a_1\lambda,&n\text{ odd}\end{cases}\]](http://latex.artofproblemsolving.com/6/7/f/67f4a48f4001e94104b68a1b896bfe774ac6399a.png)
as desired.Stanley Chapter 1 Exercise 5 wrote:
Let 
be the complete bipartite graph 
with vertex-disjoint edges removed. Thus has 
vertices and 
edges, each of degree 
. Show that the eigenvalues of are 
( times each) and 
(once each).
be the complete bipartite graph 
with vertex-disjoint edges removed. Thus has 
vertices and 
edges, each of degree 
. Show that the eigenvalues of are 
( times each) and 
(once each).
.
through 
(or rather the edge set of 
.
for all 
and 
by our labeling system. Furthermore, note that with respect to the remaining entries of 
and 
entries. Thus, we can conclude that our adjacency matrix has the form ![\[A(H_n)=\begin{bmatrix}0&J-I\\J-I&0\end{bmatrix},\]](http://latex.artofproblemsolving.com/e/2/a/e2a26a1cbe4424be2f66c73e6ad8c1b506f624e7.png)
where 
is the matrix with all ones. For example, when 
,![\[A(H_3)=\begin{bmatrix}0&0&0&0&1&1\\0&0&0&1&0&1\\0&0&0&1&1&0\\0&1&1&0&0&0\\1&0&1&0&0&0\\1&1&0&0&0&0\end{bmatrix}.\]](http://latex.artofproblemsolving.com/8/1/4/814a7f4fdebf592fbb01cc9938a1a22b9c424f10.png)
To compute the eigenvalues of this matrix, recall that if 
,
are square blocks, then ![\[\det\begin{bmatrix}A&B\\C&D\end{bmatrix}=\det(AD-BC).\]](http://latex.artofproblemsolving.com/b/8/d/b8d4d9c6c2a3330125112ce4015dc1941498967d.png)
(I seriously need to find the proof for this....) Now for any 
,![\[\det[A(H_n)-\lambda I]=\det\begin{bmatrix}-\lambda I&J-I\\J-I&-\lambda I\end{bmatrix}=\det(\lambda^2 I-(J-I)^2).\]](http://latex.artofproblemsolving.com/b/3/7/b370ae17dcf086beed2fcc66a08be1775733f5df.png)
Using the fact that 
and 
(why?), remark that ![\[(J-I)^2=J^2-2IJ+I^2=nJ-2J+I=(n-2)J+I.\]](http://latex.artofproblemsolving.com/c/1/6/c1617138d9534169849f87c324b1c04db275f5b7.png)
Thus ![\[\det[\lambda^2I^2-(I-J)^2]=0\iff \det[J(n-2)-(\lambda^2-1)I]=(n-2)\det\left[J-\left(\dfrac{\lambda^2-1}{n-2}\right)I\right]=0.\]](http://latex.artofproblemsolving.com/5/f/c/5fc0303606b034131782d5bef51af3b11ccc1cb4.png)
(This obviously cannot be done for 
,
,
,
.
,
is an eigenvalue of 
with multiplicity 
with multiplicity ![\[0=\dfrac{\lambda^2-1}{n-2}\quad\implies\quad \lambda=\pm 1\]](http://latex.artofproblemsolving.com/f/d/4/fd4cb25bd43145c02075662040c0c6534a42c021.png)
or ![\[n=\dfrac{\lambda^2-1}{n-2}\quad\implies\quad \lambda=\pm (n-1)\]](http://latex.artofproblemsolving.com/8/b/6/8b6fc12824058a8daec4b1f152759838178c2454.png)
and it's not hard to show that these roots have the desired multiplicities, so we're done.Stanley Chapter 1 Problem 11 wrote:
Let 
denote the complete graph with vertices, with one loop at each vertex. Let 
denote with the edges of 
removed, i.e. choose 
vertices of and remove all edges between these vertices (including loops). Find the number 
of closed walks in 
of length .
denote the complete graph with vertices, with one loop at each vertex. Let 
denote with the edges of 
removed, i.e. choose 
vertices of and remove all edges between these vertices (including loops). Find the number 
of closed walks in 
of length .
in an advantageous manner and then consult its adjacency matrix. WLOG number the vertices 
such that the three vertices not chosen in 
are 
.![\[A(\Gamma)=\begin{bmatrix}1&1&1&1&\cdots&1\\1&1&1&1&\cdots&1\\1&1&1&1&\cdots&1\\1&1&1&0&\cdots&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\1&1&1&0&\cdots&0\end{bmatrix}.\]](http://latex.artofproblemsolving.com/5/d/6/5d612a821e14544e1b46b9e00e6c6b80ad1e61a5.png)
In other words, 
consists of two bands of 
,
are the squares of the eigenvalues of the original matrix 
.![\[(A(\Gamma)^2)_{ii}=\sum_jA(\Gamma)_{ij}A(\Gamma)_{ji}.\]](http://latex.artofproblemsolving.com/4/a/b/4aba38c4fceac3aa8ecdc88459315541be9f3993.png)
If 
,
or 
are equal to 
.![\[A(\Gamma)^2=\begin{bmatrix}21&*&*&*&\cdots&*\\ *&21&*&*&\cdots&*\\ *&*&21&*&\cdots&*\\ *&*&*&3&\cdots&*\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ *&*&*&*&\cdots&3\end{bmatrix},\]](http://latex.artofproblemsolving.com/c/6/d/c6dc774563d73ce0efdfcb3dcf8584d8c072c859.png)
meaning that 
be the two nonzero eigenvalues of 
trivially, we get the system of equations ![\[\begin{cases}\lambda_1+\lambda_2&=3,\\\lambda_1^2+\lambda_2^2&=117.\end{cases}\]](http://latex.artofproblemsolving.com/f/0/8/f08a1408ad8ac1d4a9360467081500d5c0f343cb.png)
Solving yields 
.Stanley Chapter 1 Exercise 12 wrote:
- Let be a finite graph and let
be the maximum degree of any vertex of . Let 
be the largest eigenvalue of the adjacency matrix . Show that 
. - Suppose that is simple (no loops or multiple edges) and has a total of
edges. Show that 
.
be the maximum degree of any vertex of 
.
edges. Show that 
.
be an eigenvector of 
be the largest entry in ![\[(A\vec{x})_i=\sum_jA_{ij}x_j\leq\sum_jA_{ij}x_i=x_i\sum_jA_{ij}\leq\Delta x_i.\]](http://latex.artofproblemsolving.com/e/0/5/e056c8c176b3eefc0cec784f90843cbfe041dd84.png)
But since 
.
for any eigenvalue 
.
,
.
,
,
the entries of ![\[\sum_{i=1}^n\left(\sum_jA_{ij}x_j\right)^2\leq 2q\sum_{j=1}^nx_j^2.\]](http://latex.artofproblemsolving.com/6/5/c/65c4cb4d0e6998e5c58523f188593f1633faf98b.png)
Once this is proven, the LHS becomes 
while the right becomes 
,![\[\sum_{j=1}^nA_{ij}^2\sum_{j=1}^nx_{ij}^2\geq\left(\sum_{j=1}^nA_{ij}x_j\right)^2.\]](http://latex.artofproblemsolving.com/0/3/b/03b7115e1f3dccb7e59531468db915aed07ee26a.png)
Summing over all ![\[\sum_{i=1}^n\left(\sum_{j=1}^nA_{ij}x_j\right)^2\leq\sum_{i=1}^n\left(\sum_{j=1}^nA_{ij}^2\sum_{j=1}^nx_j^2\right)\leq\left(\sum_{i,j}A_{ij}^2\right)\left(\sum_{j=1}^nx_j^2\right).\]](http://latex.artofproblemsolving.com/b/c/5/bc5ee2b5ffbf393bb8cbfb01ded4045cee3b4655.png)
Finally, remark that since all entries in 
simply equals the sum of the entries in This post has been edited 3 times. Last edited by djmathman, Dec 28, 2015, 5:03 AM
April 2025
November 2024