See background page .
I asked you to do three homework problems for next Tuesday:
I'm restating the problems for homework since the second one
was misstated. Also, I'm including a hint for the third problem.
(1) Show that if mu is an eigenvalue of a bipartite graph G,
then -mu is also an eigenvalue.
This problem can be done directly as indicated in the text.
However, you should note a useful property of bipartite graphs:
A bipartite graph has a vertex ordering in which all vxs of
the first type occur first, followed by all those of the
second type. Hence, its adjacency matrix, with the suitable
ordering of rows and columns, is a 2x2 block matrix in which
only the two non-diagonal blocks are non-zero.
(2) If M is a matrix with the property that all elements
are positive, then the Perron-Frobenius Theorem says that
there is an all-positive vector x which is a right eigenvector
of the unique maximum real eigenvalue mu_max. (One calls the
max eigenvalue (and such an all-positive eigenvector associated
with this eigenvalue) the _dominant_ eigenvalue and eigenvector
of the positive matrix M.
Now suppose that, in addition to being positive, M = (m_ij)
satisfies the property that m_ji is 1/m_ij (called being
"inverse-symmetric").
Find the left eigenvector of mu_max which naturally corresponds
to the dominant (right) eigenvector of mu_max. The left
eigenvectors are row vectors while the right eigenvectors are
column vectors. That is, if M x = mu x, with mu = mu_max and x > 0,
find y such that y^t M = mu y^t. ("^t" denotes "transpose".)
(3) Let K_p,q denote the complete bipartite graph with p
vertices of type 1 and q vertices of type 2, where edges
join each vx of type 1 to each vx of type 2 and no two
edges of the same type are adjacent. The question was to
find the characteristic polynomial of K_p,q, and to prove
that the formula always works.
Here is a hint for the third problem. There may be other
ways to do it but the hint below uses several basic facts
about matrices which it is helpful to know.
HINT:
What can you say about the rank of the adjacency matrix
of a bipartite graph? Now make an inference about the
multiplicity of zero as an eigenvalue. This tells you
that the characteristic polynomial in x has a factor of
x^r, where r is the multiplicity of zero (by definition
of eigenvalue as a root of the characteristic polynomial).
The proof concludes using Prop. 2.3.
Original statement:
(1) Let G be a bipartite graph. Show that if mu is an eigenvalue of G, then -mu is also an eigenvalue of G.
(2) Let M be a matrix with all positive entries and satisfying m_ji = (m_ij)^(-1) (i.e., the transpose of M is the same as taking the inverse of every element). Thus, the diagonal elements must all be 1 and the ij-element is the inverse of the ji-element. If V is the set of all right eigenvectors associated to the eigenvalue mu, what is the set V' of all left eigenvectors associated to mu? The right eigenvectors x satisfy Mx = mu x, while the left eigenvectors satisfy yM = mu y, so the left eigenvectors are 1 x n - i.e., row vectors - while the right eigenvectors are n x 1 and are column vectors. How are the entries in the rows vectors in V' related to the entries in the column vectors in V? Try it on a simple example.
(3) Find the characteristic polynomial of the complete bipartite graph K_p,q (i.e., find a formula). Now prove that it works!
You are requested to please write legibly. This means you should try the problems in advance and then copy over your answer - do leave in your work, of course, so I can see how you got your results. So ideally you can staple together what you've done, with at least a readable summary. For the proofs, which we won't be emphasizing but these have some helpful techniques, you should try to sketch the main idea but don't worry about being exhaustive and detailed.
Back to the index page