User hypercube - MathOverflow

Positive semidefinite decomposition, Laplacian eigenvalues, and the oriented incidence matrix

2012-03-09T17:46:40Z

Suppose $A\in\mathbb{C}^{n\times n}$ is Hermitian and positive semidefinite with some decomposition $A=BB^*$, where $B=(b_{ij})\in\mathbb{C}^{n\times m}$ (not necessarily the Cholesky decomposition).

Question: is there a nice relationship between the row/column sums of $B$ and the eigenvalues of $A$? Specifically, can we obtain lower bounds for the largest eigenvalue of $A$ with the one of the following forms (or similar in nature):

(1) $\displaystyle\max_{1\leq j\leq n}\sum_{k=1}^mb_{jk}$ + $\displaystyle\min_{1\leq k\leq m}\sum_{j=1}^n b_{jk}$ - 1 $\leq \lambda_{\max}(A)$.

(2) $\displaystyle\max_{1\leq j\leq n}\sum_{k=1}^m|b_{jk}|$ + $\displaystyle\min_{1\leq k\leq m}\sum_{j=1}^n |b_{jk}|$ - 1 $\leq \lambda_{\max}(A)$.

Obviously $B$ would need to have some special condition in (1) to make sure these sums are real. Perhaps this is too strong, but it would be useful to have such a relationship. Here is some possible motivation:

The Laplacian matrix of a simple graph $G$ can be written as $L(G)=B(G)B(G)^{\text{T}}$, where $B$ is the oriented incidence matrix of $G$. The suggested lower bound (2) produces the well known bound:

$\Delta+2-1=\Delta+1\leq \lambda_{\max}(L(G))$.

So I suppose the question can be thought of as: is there a nice relationship between the oriented incidence matrix row/column sums and the Laplacian eigenvalues similar to (1) and (2)?

Spectral radius of a proper subgraph

2011-07-08T17:14:49Z

I came across a Chinese reference in the paper "On the spectral radius of trees with ﬁxed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of graphs", Acta Math. Appl. Sinica 2 (1979) 167–175.

Let $\lambda_1(H)$ be the spectral radius of the adjacency matrix of the graph H.

Let $G$ be a connected graph, and let $G'$ be a proper subgraph of $G$. Then $\lambda_1(G)>\lambda_1(G')$.

1) Is there a trivial argument of this using interlacing or is something more sophisticated needed here.

2) Is this also true for the Laplacian spectral radius. I assume if there is an interlacing argument this will be trivial.

What are some interesting grading/curving systems you have seen for a course?

2010-12-13T16:29:48Z

It seems like every math course has something unique in how things are graded.

1) What are some interesting grading systems you have seen/used? (include curving types, etc.)

2) What are some pros and cons to this particular system?

3) Would you use it again if you have used it yourself?

One system for grading a final exam that I recently came across was this.

Answer by hypercube for The Matrix Tree Theorem for Weighted Graphs.

2010-12-12T22:21:09Z

For signed graphs we have an interesting matrix-tree theorem. A signed graph is a graph with the additional structure of edge signs (weights) being either +1 or -1. We say that a cycle in a signed graph is balanced if the product of the edges in the cycle is +1. A signed graph is balanced if all of its cycles are balanced. Otherise, we say a signed graph is unbalanced.

We say a subgraph $H$ of a connected signed graph $G$ is an essential spanning tree of $\Gamma$ if either

1) $\Gamma$ is balanced and $H$ is a spanning tree of $G$, or

2) $\Gamma$ is unbalanced, $H$ is a spanning subgraph and every component of $H$ is a unicyclic graph with the unique cycle having sign -1.

The matrix-tree theorem for signed graphs is stated as follows:

Let $G$ be a connected signed graph with $N$ vertices and let $b_k$ be the number of essential spanning subgraphs which contain $k$ negative cycles. Then

$$ \det(L(G))=\sum_{k=0}^n 4^k b_k.$$

For some references see:

T. Zaslavsky, Signed Graphs, Discrete Appl. Math, 4 (1982), 47-74.

S. Chaiken, A combinatorial proof of the all minors matrix tree theorem. SIAM J. Algebraic Discrete Methods, 3 (1982), 319-329.

Signed graphs are used in spin glass theory and network applications.

Considering mixed graphs, which are directed graphs that have some edges as undirected, we actually get the same theory. This is immediate since the matrix definitions are identical for signed graphs and mixed graphs. This seems to escape many of the people studying matrix properties of mixed graphs however. See:

R. Bapat, J. Grossman and D. Kilkarni, Generalized Matrix Tree Theorem for Mixed Graphs, Lin. and Mult. Lin. Algebra, 46 (1999), 299-312.

Complex root systems

2010-12-11T02:48:01Z

This question is twofold.

1) What is the best reference on root systems?

2) Do complex root systems exist?

Weighted Polytope

2010-12-10T05:42:28Z

I am curious if this kind of construction (or something similar) exists:

Consider a convex polytope $P$ and then consider the graph of the polytope $G(P)$ (1-skeleton). Suppose a weighting structure is given to this graph now. So we have a pair $(G(P),w)$ with $w:E(G(P))\rightarrow \mathbb{R}$. We construct a weighting on the polytope $P$ as follows.

First consider a 2-face $F$ bounded by edges $e_1,\ldots,e_k$. We assign the weight $w(F)=\prod_{i=1}^k w(e_i)$.

Continuing in the obvious manner we have a $j+1$-face $F'$ bounded by $j$-faces $F_1,\ldots,F_m$ has weight $w(F')=\prod_{i=1}^m w(F_i)$.

This particular weighting structure is interesting because it seems like a natural generalization of signed-graphs (weighting on the edges is either $+1$ or $-1$) to polytopes.

Are there any interesting weighting structures out there for polytopes?

Answer by hypercube for Spectrum of the Laplacian on G(n, p) and G(n, M)

2010-12-10T05:13:13Z

You might find this paper and the references therein useful:

Amin Coja-Oghlan, On the Laplacian eigenvalues of $G_{n,p}$, Combin. Probab. Comput., 16 (2007). MR 2008j:05212.

They discuss the classical model as well as Chung and Lu's model which is quite interesting.

Generalized Courant-Fischer theorem

2010-11-30T20:58:26Z

Consider some quaternionic matrix $A$. A right eigvenvalue of $A$ is a quaternion $q$ such that $Ax=xq$ for some $x\in \mathbb{H}^n$. Similarly, a left eigenvalue of $A$ is quaternion $q$ such that $Ax=qx$ for some $x\in \mathbb{H}^n$.

I am curious if there is a generalized version of the Courant-Fischer (min-max) theorem for the right eigenvalues of Hermitian quaternionic matrices. It is known that for a Hermitian quaternionic matrix the right eigenvalues are real. This is the case I am most interested in.

For a good starting place in the references see: Fuzhen Zhang, Quaternions and matrices of quaternions, Linear Algebra Appl., 251 (1997), 21--57. MR 1421264 (97h:15020).

Answer by hypercube for When are Ehrhart polynomials polynomials?

2010-06-08T02:22:49Z

If you want to dive into some Ehrhart theory then I highly recommend you pick up Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra by Matthias Beck and Sinai Robins.

Here is the website for the text with a free but nonprintable version: http://math.sfsu.edu/beck/ccd.html

Answer by hypercube for Why does undergraduate discrete math require calculus?

2010-06-04T21:19:49Z

Although calculus is not frequently used in discrete mathematics it is nice to know that the students have had at least some exposure to sets and functions. I am teaching discrete this summer and find myself saying "you have seen this in calculus" when talking about several fundamental concepts.

When doing proofs in a calculus course I usually try to point out the fundamental concepts from the course that are needed and in a discrete course the actual process of how do do a proof is studied more closely. Again it is nice to know that at least the students have seen proofs before and we can build on this exposure.

Answer by hypercube for What's your favorite equation, formula, identity or inequality?

2010-06-02T19:22:27Z

$\sum_{i=1}^m \sum_{j=1}^n a_{ij} = \sum_{j=1}^n \sum_{i=1}^m a_{ij}$

Answer by hypercube for Is there an image for you that epitomizes mathematics?

2010-06-02T13:20:32Z

A proof without words for the Pythagorean theorem (Zhou Bi Suan Jing).

Answer by hypercube for What introductory book on Graph Theory would you recommend?

2010-05-28T12:47:23Z

Graphs & digraphs by Gary Chartrand and Linda Lesniak is very well written. The organization is nice and the proofs are very clear. Moreover the exercises are concrete and to the point.

Answer by hypercube for What introductory book on Graph Theory would you recommend?

2010-05-28T04:42:59Z

Pearls in Graph Theory: A Comprehensive Introduction by Nora Hartsfield and Gerhard Ringel. This is a great introductory book and is one of the better dover books out there in my opinion.

Answer by hypercube for Linear Algebra Texts?

2010-05-22T19:01:35Z

Newer Books

Matrix Analysis and Applied Linear Algebra by Meyer is very well written with clear cut examples and exercises. I think this would make an excellent first course.

I agree also that Axler's books is a great text for the more mature.

Classics

Finite-Dimensional Vector Spaces by P. R. Halmos is an absolute essential for the budding mathematician in my opinion. This is because of the exercises (My recommendation: solve all of them).

As mentioned above Linear Algebra (2nd Edition) by Kenneth M Hoffman and Ray Kunze. This may be my favorite text because of its volume of content.

More Advanced

Advanced Linear Algebra by Steven Roman

Matrix Analysis

Matrix Analysis and Topics in Matrix Analysis by Roger A. Horn and Charles R. Johnson

Matrix Analysis by Rajendra Bhatia

Answer by hypercube for Genealogy of the Lagrange inversion theorem

2010-05-21T18:26:41Z

Richard Stanley has written some excellent notes in EC2 ch. 5 p67 about the Lagrange inversion formula (Theorem 5.4.2 on p38).

Stanley provides reference to An introduction to the theory of infinite series by Thomas John I'Anson Bromwich (You can see the full 1908 text through google books and other editions here: http://books.google.com/books?q=editions:UOM39015064521290&id=ZY45AAAAMAAJ) where several applications are provided.

Stanley also provides reference for generalizations of the Lagrange inversion formula:

I.M. Gessel's Paper (combinatorial proof): http://portal.acm.org/citation.cfm?id=31572 Note: Gessel also gives a generalization of Lagrange inversion to noncommutative power series in A noncommutative generalization and q-analog of the Lagrange inversion formula.

See also D.W. Stanton's Survey: Recent results for the q-Lagrange inversion formula.

Answer by hypercube for What out-of-print books would you like to see re-printed?

2010-05-21T17:57:15Z

Topology by James Dugundji
General Topology by Ryszard Engelking
Topology - Volumes I and II by Kazimierz Kuratowski

Answer by hypercube for Texts on the General History of Contemporary Combinatorics

2010-05-20T14:40:25Z

In Richard Stanley's EC1 and EC2 he provides some notes at the end of each chapter with some interesting historical remarks and references.

Comment by hypercube

2012-03-30T20:27:46Z

Hi Felix, I know of the Grone-Merris conjecture as well as Bai's work on it (if you want a neat reference that is quite new: homepages.cwi.nl/~aeb/math/ipm.pdf). However, I am more interested if the matrix result above is true.

Comment by hypercube

2010-12-11T16:58:59Z

Wow! Thanks for all that information Jim.

Comment by hypercube

2010-12-11T04:13:59Z

Thanks for the quick reply.

Comment by hypercube

2010-12-10T15:37:11Z

These are some interesting remarks, thanks! This is motivated by signed graphs. The most interesting parameter when studying signed graphs is the concept of "balance." We say a cycle in a signed graph is balanced if the product of its edges is +1. A signed graph is balanced if all of its cycles are balanced. This leads to many interesting things like a generalization of graphic matroids, hyperplane arrangements, root systems, etc. If you consider a weighting of +1/-1 on the vertices this actually provides a method of changing the edge signs without affecting balance, called "switching".

Comment by hypercube

2010-12-10T05:55:57Z

This is homework.

Comment by hypercube

2010-12-10T04:52:28Z

Perhaps you should tag it as reference-request then.

Comment by hypercube

2010-12-10T04:47:46Z

I found an interesting paper: M. Seetharama Gowda and J. Tao, The Cauchy interlacing theorem in simple Euclidean Jordan algebras and some consequences. Which can be found here: math.umbc.edu/~gowda/tech-reports/trGOW08-02.pdf. However I am looking for a form of the Courant-Fischer theorem in which we would take maxs/mins over vectors in H^n.

Comment by hypercube

2010-12-03T18:52:03Z

The video lectures here: cs.princeton.edu/theory/index.php/Main/… are also relevant.

Comment by hypercube

2010-06-05T19:58:56Z

It does not shock me really. What I meant was that even if they see a sketch of a proof they at least have some exposure to the process.

Comment by hypercube

2010-06-02T19:12:09Z

Adding to this here is a webpage for the Thompson groups seminar at Binghamton led by Matt Brin: math.binghamton.edu/matt/thompson/index.html

Comment by hypercube

2010-05-28T05:46:23Z

sp correction: matroids

Comment by hypercube

2010-05-26T22:52:48Z

On my office door I once put "clopen the door"

Comment by hypercube

2010-05-22T18:43:38Z

Blast, you beat me to this. I thought it was a nice read as well. His development of K-theory is also interesting: math.rutgers.edu/~weibel/papers-dir/khistory.pdf

Comment by hypercube

2010-05-22T18:36:44Z

I'm assuming by the work of Biggs you mean Graph Theory 1736-1936 (with E.K. Lloyd and R.J. Wilson). Oxford University Press, 1976. Second edition 1986, Japanese edition 1986. I would like to read this myself someday since I have only heard good things about it.