User hypercube - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:42:41Z http://mathoverflow.net/feeds/user/6209 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90740/positive-semidefinite-decomposition-laplacian-eigenvalues-and-the-oriented-inci Positive semidefinite decomposition, Laplacian eigenvalues, and the oriented incidence matrix hypercube 2012-03-09T17:46:40Z 2012-05-11T15:22:01Z <p>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). </p> <p><b>Question</b>: 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):</p> <p>(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)$.</p> <p>OR</p> <p>(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)$.</p> <p>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:</p> <p>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:</p> <p>$\Delta+2-1=\Delta+1\leq \lambda_{\max}(L(G))$.</p> <p>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)?</p> http://mathoverflow.net/questions/69807/spectral-radius-of-a-proper-subgraph Spectral radius of a proper subgraph hypercube 2011-07-08T17:14:49Z 2011-07-16T08:18:12Z <p>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. </p> <p>Let $\lambda_1(H)$ be the spectral radius of the adjacency matrix of the graph H.</p> <p>Let $G$ be a connected graph, and let $G'$ be a proper subgraph of $G$. Then $\lambda_1(G)>\lambda_1(G')$. </p> <p>1) Is there a trivial argument of this using interlacing or is something more sophisticated needed here.</p> <p>2) Is this also true for the Laplacian spectral radius. I assume if there is an interlacing argument this will be trivial.</p> http://mathoverflow.net/questions/49275/what-are-some-interesting-grading-curving-systems-you-have-seen-for-a-course What are some interesting grading/curving systems you have seen for a course? hypercube 2010-12-13T16:29:48Z 2010-12-13T18:36:11Z <p>It seems like every math course has something unique in how things are graded. </p> <p>1) What are some interesting grading systems you have seen/used? (include curving types, etc.)</p> <p>2) What are some pros and cons to this particular system? </p> <p>3) Would you use it again if you have used it yourself?</p> <p>One system for grading a final exam that I recently came across was <a href="http://www.math.uwaterloo.ca/~kpurbhoo/co630/pageonefinal.pdf" rel="nofollow">this</a>.</p> http://mathoverflow.net/questions/10493/the-matrix-tree-theorem-for-weighted-graphs/49179#49179 Answer by hypercube for The Matrix Tree Theorem for Weighted Graphs. hypercube 2010-12-12T22:21:09Z 2010-12-12T22:21:09Z <p>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 <i>balanced</i> if the product of the edges in the cycle is +1. A signed graph is <i>balanced</i> if all of its cycles are balanced. Otherise, we say a signed graph is unbalanced.</p> <p>We say a subgraph $H$ of a connected signed graph $G$ is an <i>essential spanning tree</i> of $\Gamma$ if either </p> <p>1) $\Gamma$ is balanced and $H$ is a spanning tree of $G$, or</p> <p>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.</p> <p>The matrix-tree theorem for signed graphs is stated as follows: </p> <p>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</p> <p>$$\det(L(G))=\sum_{k=0}^n 4^k b_k.$$</p> <p>For some references see:</p> <p>T. Zaslavsky, Signed Graphs, <i>Discrete Appl. Math</i>, <b>4</b> (1982), 47-74.</p> <p>S. Chaiken, A combinatorial proof of the all minors matrix tree theorem. <i>SIAM J. Algebraic Discrete Methods</i>, <b>3</b> (1982), 319-329.</p> <p>Signed graphs are used in spin glass theory and network applications.</p> <p>Considering <i>mixed graphs</i>, 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:</p> <p>R. Bapat, J. Grossman and D. Kilkarni, Generalized Matrix Tree Theorem for Mixed Graphs, <i>Lin. and Mult. Lin. Algebra</i>, <b>46</b> (1999), 299-312.</p> http://mathoverflow.net/questions/49008/complex-root-systems Complex root systems hypercube 2010-12-11T02:48:01Z 2010-12-11T15:08:06Z <p>This question is twofold.</p> <p>1) What is the best reference on root systems?</p> <p>2) Do complex root systems exist?</p> http://mathoverflow.net/questions/48882/weighted-polytope Weighted Polytope hypercube 2010-12-10T05:42:28Z 2010-12-10T12:58:00Z <p>I am curious if this kind of construction (or something similar) exists:</p> <p>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.</p> <p>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)$.</p> <p>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)$. </p> <p>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.</p> <p>Are there any interesting weighting structures out there for polytopes?</p> http://mathoverflow.net/questions/47711/spectrum-of-the-laplacian-on-gn-p-and-gn-m/48879#48879 Answer by hypercube for Spectrum of the Laplacian on G(n, p) and G(n, M) hypercube 2010-12-10T05:13:13Z 2010-12-10T05:13:13Z <p>You might find this paper and the references therein useful:</p> <p>Amin Coja-Oghlan, On the Laplacian eigenvalues of $G_{n,p}$, <i>Combin. Probab. Comput</i>., <b>16</b> (2007). MR 2008j:05212.</p> <p>They discuss the classical model as well as Chung and Lu's model which is quite interesting.</p> http://mathoverflow.net/questions/47833/generalized-courant-fischer-theorem Generalized Courant-Fischer theorem hypercube 2010-11-30T20:58:26Z 2010-12-10T04:53:45Z <p>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$.</p> <p>I am curious if there is a generalized version of the <a href="http://en.wikipedia.org/wiki/Min-max_theorem" rel="nofollow"> Courant-Fischer (min-max) theorem</a> 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.</p> <p>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).</p> http://mathoverflow.net/questions/27413/when-are-ehrhart-polynomials-polynomials/27419#27419 Answer by hypercube for When are Ehrhart polynomials polynomials? hypercube 2010-06-08T02:22:49Z 2010-06-08T02:22:49Z <p>If you want to dive into some Ehrhart theory then I highly recommend you pick up <em>Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra</em> by Matthias Beck and Sinai Robins.</p> <p>Here is the website for the text with a free but nonprintable version: <a href="http://math.sfsu.edu/beck/ccd.html" rel="nofollow">http://math.sfsu.edu/beck/ccd.html</a></p> http://mathoverflow.net/questions/27076/why-does-undergraduate-discrete-math-require-calculus/27109#27109 Answer by hypercube for Why does undergraduate discrete math require calculus? hypercube 2010-06-04T21:19:49Z 2010-06-04T21:19:49Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/3134/whats-your-favorite-equation-formula-identity-or-inequality/26855#26855 Answer by hypercube for What's your favorite equation, formula, identity or inequality? hypercube 2010-06-02T19:22:27Z 2010-06-02T19:22:27Z <p>$\sum_{i=1}^m \sum_{j=1}^n a_{ij} = \sum_{j=1}^n \sum_{i=1}^m a_{ij}$</p> http://mathoverflow.net/questions/2437/is-there-an-image-for-you-that-epitomizes-mathematics/26819#26819 Answer by hypercube for Is there an image for you that epitomizes mathematics? hypercube 2010-06-02T13:20:32Z 2010-06-02T17:44:07Z <p>A proof without words for the Pythagorean theorem (Zhou Bi Suan Jing).</p> <p><img src="http://upload.wikimedia.org/wikipedia/commons/c/c3/Chinese_pythagoras.jpg" height="450"></p> http://mathoverflow.net/questions/4836/what-introductory-book-on-graph-theory-would-you-recommend/26255#26255 Answer by hypercube for What introductory book on Graph Theory would you recommend? hypercube 2010-05-28T12:47:23Z 2010-05-28T12:47:23Z <p><em>Graphs &amp; digraphs</em> 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.</p> http://mathoverflow.net/questions/4836/what-introductory-book-on-graph-theory-would-you-recommend/26226#26226 Answer by hypercube for What introductory book on Graph Theory would you recommend? hypercube 2010-05-28T04:42:59Z 2010-05-28T04:42:59Z <p><em>Pearls in Graph Theory: A Comprehensive Introduction</em> 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.</p> http://mathoverflow.net/questions/16994/linear-algebra-texts/25596#25596 Answer by hypercube for Linear Algebra Texts? hypercube 2010-05-22T19:01:35Z 2010-05-22T19:01:35Z <p><strong>Newer Books</strong></p> <p><em>Matrix Analysis and Applied Linear Algebra</em> by Meyer is very well written with clear cut examples and exercises. I think this would make an excellent first course.</p> <p>I agree also that Axler's books is a great text for the more mature.</p> <p><strong>Classics</strong></p> <p><em>Finite-Dimensional Vector Spaces</em> 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).</p> <p>As mentioned above <em>Linear Algebra (2nd Edition)</em> by Kenneth M Hoffman and Ray Kunze. This may be my favorite text because of its volume of content.</p> <p><strong>More Advanced</strong></p> <p><em>Advanced Linear Algebra</em> by Steven Roman </p> <p><strong>Matrix Analysis</strong></p> <p><em>Matrix Analysis</em> and <em>Topics in Matrix Analysis</em> by Roger A. Horn and Charles R. Johnson </p> <p><em>Matrix Analysis</em> by Rajendra Bhatia</p> http://mathoverflow.net/questions/25491/genealogy-of-the-lagrange-inversion-theorem/25522#25522 Answer by hypercube for Genealogy of the Lagrange inversion theorem hypercube 2010-05-21T18:26:41Z 2010-05-21T19:07:03Z <p>Richard Stanley has written some excellent notes in EC2 ch. 5 p67 about the Lagrange inversion formula (Theorem 5.4.2 on p38).</p> <p>Stanley provides reference to <em>An introduction to the theory of infinite series</em> by Thomas John I'Anson Bromwich (You can see the full 1908 text through google books and other editions here: <a href="http://books.google.com/books?q=editions:UOM39015064521290&amp;id=ZY45AAAAMAAJ" rel="nofollow">http://books.google.com/books?q=editions:UOM39015064521290&amp;id=ZY45AAAAMAAJ</a>) where several applications are provided.</p> <p>Stanley also provides reference for generalizations of the Lagrange inversion formula:</p> <p>I.M. Gessel's Paper (combinatorial proof): <a href="http://portal.acm.org/citation.cfm?id=31572" rel="nofollow">http://portal.acm.org/citation.cfm?id=31572</a> Note: Gessel also gives a generalization of Lagrange inversion to noncommutative power series in <em>A noncommutative generalization and q-analog of the Lagrange inversion formula</em>.</p> <p>See also D.W. Stanton's Survey: <em>Recent results for the q-Lagrange inversion formula</em>.</p> http://mathoverflow.net/questions/18271/what-out-of-print-books-would-you-like-to-see-re-printed/25515#25515 Answer by hypercube for What out-of-print books would you like to see re-printed? hypercube 2010-05-21T17:57:15Z 2010-05-21T18:03:31Z <ol> <li><em>Topology</em> by James Dugundji</li> <li><em>General Topology</em> by Ryszard Engelking</li> <li><em>Topology - Volumes I and II</em> by Kazimierz Kuratowski</li> </ol> http://mathoverflow.net/questions/25169/texts-on-the-general-history-of-contemporary-combinatorics/25373#25373 Answer by hypercube for Texts on the General History of Contemporary Combinatorics hypercube 2010-05-20T14:40:25Z 2010-05-20T14:40:25Z <p>In Richard Stanley's EC1 and EC2 he provides some notes at the end of each chapter with some interesting historical remarks and references.</p> http://mathoverflow.net/questions/90740/positive-semidefinite-decomposition-laplacian-eigenvalues-and-the-oriented-inci/92667#92667 Comment by hypercube hypercube 2012-03-30T20:27:46Z 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: <a href="http://homepages.cwi.nl/~aeb/math/ipm.pdf" rel="nofollow">homepages.cwi.nl/~aeb/math/ipm.pdf</a>). However, I am more interested if the matrix result above is true. http://mathoverflow.net/questions/49008/complex-root-systems/49050#49050 Comment by hypercube hypercube 2010-12-11T16:58:59Z 2010-12-11T16:58:59Z Wow! Thanks for all that information Jim. http://mathoverflow.net/questions/49008/complex-root-systems/49011#49011 Comment by hypercube hypercube 2010-12-11T04:13:59Z 2010-12-11T04:13:59Z Thanks for the quick reply. http://mathoverflow.net/questions/48882/weighted-polytope/48915#48915 Comment by hypercube hypercube 2010-12-10T15:37:11Z 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 &quot;balance.&quot; 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 &quot;switching&quot;. http://mathoverflow.net/questions/48884/on-the-product-of-two-positive-definite-matrices Comment by hypercube hypercube 2010-12-10T05:55:57Z 2010-12-10T05:55:57Z This is homework. http://mathoverflow.net/questions/48876/algebraic-k-groups-and-braids Comment by hypercube hypercube 2010-12-10T04:52:28Z 2010-12-10T04:52:28Z Perhaps you should tag it as reference-request then. http://mathoverflow.net/questions/47833/generalized-courant-fischer-theorem Comment by hypercube hypercube 2010-12-10T04:47:46Z 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: <a href="http://www.math.umbc.edu/~gowda/tech-reports/trGOW08-02.pdf" rel="nofollow">math.umbc.edu/~gowda/tech-reports/trGOW08-02.pdf</a>. However I am looking for a form of the Courant-Fischer theorem in which we would take maxs/mins over vectors in H^n. http://mathoverflow.net/questions/46785/a-learning-roadmap-for-additive-combinatorics/46807#46807 Comment by hypercube hypercube 2010-12-03T18:52:03Z 2010-12-03T18:52:03Z The video lectures here: <a href="http://www.cs.princeton.edu/theory/index.php/Main/AdditiveCombinatoricsMinicourse" rel="nofollow">cs.princeton.edu/theory/index.php/Main/&hellip;</a> are also relevant. http://mathoverflow.net/questions/27076/why-does-undergraduate-discrete-math-require-calculus/27109#27109 Comment by hypercube hypercube 2010-06-05T19:58:56Z 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. http://mathoverflow.net/questions/26821/is-thompsons-group-f-amenable/26847#26847 Comment by hypercube hypercube 2010-06-02T19:12:09Z 2010-06-02T19:12:09Z Adding to this here is a webpage for the Thompson groups seminar at Binghamton led by Matt Brin: <a href="http://www.math.binghamton.edu/matt/thompson/index.html" rel="nofollow">math.binghamton.edu/matt/thompson/index.html</a> http://mathoverflow.net/questions/4836/what-introductory-book-on-graph-theory-would-you-recommend/26230#26230 Comment by hypercube hypercube 2010-05-28T05:46:23Z 2010-05-28T05:46:23Z sp correction: matroids http://mathoverflow.net/questions/23478/examples-of-common-false-beliefs-in-mathematics/23580#23580 Comment by hypercube hypercube 2010-05-26T22:52:48Z 2010-05-26T22:52:48Z On my office door I once put &quot;clopen the door&quot; http://mathoverflow.net/questions/23643/books-about-history-of-recent-mathematics/23661#23661 Comment by hypercube hypercube 2010-05-22T18:43:38Z 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: <a href="http://www.math.rutgers.edu/~weibel/papers-dir/khistory.pdf" rel="nofollow">math.rutgers.edu/~weibel/papers-dir/khistory.pdf</a> http://mathoverflow.net/questions/25169/texts-on-the-general-history-of-contemporary-combinatorics Comment by hypercube hypercube 2010-05-22T18:36:44Z 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.