User felix goldberg - MathOverflow

Incidence matrices of generalized quadrangles

2013-05-08T19:45:53Z

Is there somewhere a database of incidence matrices of generalized quadrangles that one can download?

Which matrix/operator in a cone has the smallest negative spectral part?

2013-05-04T07:13:07Z

Background:

Let $\mathcal{K}$ be set (convex cone, if you like) of symmetric matrices of order $n$. Each matrix $A \in \mathcal{K}$ can be decomposed in a unique way as $A=A_{+}-A_{-}$, where $A_{+}$ and $A_{-}$ are mutually orthogonal positive definite matrices.

The question

Let us define $m(A)=\frac{||A_{-}||}{||A||}$, using the Frobenius norm. I am interested in finding a matrix $A \in \mathcal{K}$ that maximizes $A$.

Notes:

My original motivation comes from the case when $\mathcal{K}$ is the set of nonnegative matrices. However, the general version at the very least seems to make sense.

Consider a (0,1) adjacency matrix of a bipartite graph. The famous Coulson-Rushbrook result says its spectrum is symmetric so we get $m(A)=1/\sqrt{2}$. This is a strong contender (optimal in the order two case, by a result of Hirriart-Urruty and Seeger), but it possible to do better in some cases...

A possible generalization could be to decompose $A$ with respect to a more general cone, instead of the cone of positive definite matrices, using Moreau decomposition.

Answer by Felix Goldberg for When can a matrix with negative entries have a completely non-negative dominant eigenvector?

2013-05-04T07:28:16Z

Basically, you are looking for matrices with the so-called "generalized Perron-Frobenius property" (there is a weak and strong version, of course, and the nuances of terminology somewhat differ in various authors). In recent years they have been studied quite a lot and - very roughly - this is equivalent to being eventually nonnegative (nonegative for some integer power).

See, for example these papers for more information, careful statements of results and examples galore:

http://www.math.uoi.gr/~dnoutsos/Noutsos_LAA_2005.pdf

http://ftp.gwdg.de/pub/misc2/EMIS/journals/ELA/ela-articles/articles/vol17_pp389-413.pdf

http://www.sciencedirect.com/science/article/pii/S002437950200366X

Counting matchings in a bipartite matching-covered graph

2013-05-02T15:21:41Z

A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & Plummer). It is well-known that for bipartite graphs this is equivalent to the existence of ear decompositions.

What I'd like to know is whether the problem of counting the perfect matchings - which is very difficult in general, even for bipartite graphs, being equivalent to the permanent etc. - becomes easier when restricted to bipartite matching-covered graphs.

For example, it seems to me that the number of matchings ought to be somehow readable off the ear-decomposition but I don't quite see how.

Lower bounds on cardinality of a union of blocks in a design

2013-05-01T14:34:05Z

Let $D$ be a $(v,k,\lambda)$-design (repeated blocks are allowed). I would like to get a lower bound on the cardinality of the union of $s$ blocks. A naive application of inclusion-exclusion gives $sk-\binom{k}{2}$ which is sometimes useful, but from the few examples I've worked out seems to be a severe underestimation of the true situation.

Has anyone treated this question befre?

If it helps, we can progressively simplify to symmetric designs and then to finite projective planes (i.e. $\lambda=1$).

Answer by Felix Goldberg for Lower bounds on cardinality of a union of blocks in a design

2013-05-01T16:59:44Z

I think a found a satisfactory answer. Using Corradi's Lemma I can show for projective planes ($\lambda=1$) that the cardinality is at least $\frac{k^{2}s}{k+s-1}$.

Computing a large permanent

2013-04-28T20:03:05Z

Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?

I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices but it's not getting anywhere with this size.

UPDT: I am thinking of the incidence matrix of an order 9 projective plane. Does that help?

Is Ryser's conjecture on permanent minimizers still open?

2013-04-25T18:03:32Z

Let $A(k,n)$ be the set of $\{0,1\}$ matrices of order $n$ with all their line sums equal to $k$.

Conjecture number 5 on the list from Minc's book, attributed to Ryser, says that if $A(k,n)$ contains incidence matrices of symmetric $(n,k,\lambda)$-designs, then the minimum permanent on $A(k,n)$ is attained at one of theses incidence matrices.

It's also number 8 on Zhan's recent list of open problems in matrix theory. As one can see there, it has been verified by Wanless up to $n=12$ but not beyond.

I wonder if, given the recent progress on permanents, there is more known now about this conjecture?

How many distinct eigenvalues does a random graph have?

2013-04-21T17:55:05Z

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one.

But what is known about the expected number of distinct eigenvalues of a random graph?

Probability that a random distance function is metric

2013-03-04T12:45:47Z

Take a random $n \times n$ nonnegative symmetric matrix $D$ with zero diagonal. What is the probability that it is an abstract distance matrix, i.e. satisfies $D_{xy}+D_{yz} \geq D_{xz}$ for all index triples $x,y,z$?

In other words: what is the probability that a nonnegative function on $V \times V$, where $V$ is some finite set, defines a finite metric space?

Answer by Felix Goldberg for Eigenvalues of directed Laplacian matrix $L$ and $DL$, where $D$ is a diagonal matrix with positive entries

2013-03-04T00:21:42Z

For undirected graphs, Theorem 2.2 in this paper might help a bit.

UPDT: Let $G$ be a weighted undirected graph with Laplacian matrix $L$. Let $D$ be a positive diagonal matrix. Let $d=min(diag(D))$ and let $\Delta$ be the maximum diagonal entry of $L$. Let $i$ be the weighted isoperimetric number of $G$. Then: $$ \lambda_{2}(DL) \geq d (\Delta-\sqrt{\Delta^{2}-i^{2}}) $$

Covering the cone of positive semidefinite matrices by intervals

2013-02-26T00:05:05Z

Is it possible to cover the cone of positive semidefinite matrices by a finite/countable/interesting family of closed intervals of matrices?

How about a general convex cone?

For the finite case the answer seems to be no but maybe there is some ingenious way I am missing.

EDIT: What I mean by interval $[A,B]$ is the set of convex combinations of the matrices $A$ and $B$. Other definitions of interval are possible, for example taking "convex combinations" with the weight scalars replaced by diagonal matrices. (like in this paper - http://www.math.wsu.edu/faculty/tsat/files/jt.pdf). Or ot can be defined entrywise, woth all matrices in the interval being entrywise greater than $A$ and less than $B$. Hope it's clearer now.

Answer by Felix Goldberg for Almost-converses to the AM-GM inequality

2013-02-24T21:02:25Z

Proposition 1 in this paper might be what you are looking for.

Largest entry of the inverse matrix?

2013-02-22T20:42:33Z

I wonder if there is a "qualitative way" of predicting from the structure ix of the matrix $A$ which entry of $A^{-1}$ will be the largest. I am specially interested in the case that $A$ is a symmetric $M$-matrix (and so $A^{-1}$ entrywise nonnegative).

There are many nice results like this for the zero pattern so I have some hope something might be possible.

The unreasonable effectiveness of Pade approximation

2013-02-21T15:12:26Z

I am trying to get an intuitive feel for why the Pade approximation works so well. Given a truncated Taylor/Maclaurin series it "extrapolates" it beyond the radius of convergence. But what I can't grasp is how it manages to approximate the original function better than the series itself does, having only "seen" the information present in the series and without having access to the original function. My naive feeling is that if you start with the Taylor series, you can't do better than it in terms of approximation error, only in terms of, say, stability or computation time. But obviously the Pade approximation does do better. So - what explains its "unreasonable effectiveness"?

UPDATE: Here is a graph from p.5 of Pade Approximants, 2nd ed., that illustrates the phenomenon that puzzles me.

trigonometric identity needed for sums involving secants

2013-02-18T22:04:00Z

I am looking for a closed-form formula for the following sum:

$\displaystyle \sum_{k=0}^{N}{\frac{\sin^{2}(\frac{k\pi}{N})}{a \cdot \sin^{2}(\frac{k\pi}{N})+1}}=\sum_{k=0}^{N}{\frac{1}{a+\csc^{2}(\frac{k\pi}{N})}}$.

Is such a formula known?

How to tell if a second-order curve goes below the $x$ axis?

2013-02-11T15:06:42Z

Suppose we have a second-order curve in general form:

(1) $a_{11}x^{2}+2a_{12}xy+a_{22}y^{2}+2a_{13}x+2a_{23}y+a_{33}=0$.

I'd like to know if there is a simple condition that ensures that the curve has at least one point on on or below the $x$ axis, i.e. that the left-hand side of (1) is nonpositive.

In the trivial case that the curve is a parabola, the discriminant being nonnegative is just such a condition. But what happens in the general case?

Tools for "bound guessing"

2012-12-11T22:45:01Z

I have a somewhat complicated symbolic expression of the form $\frac{J-a+\frac{q}{a}}{J(J-a)+q}$, where $J,a$ and $q$ are themselves affine functions of four other variables $d,r,c,s$, and I want to find some tame upper bound for the expression in terms of $d,r,c,s$. Sometimes this works well by simplifying the original expression with the use of a symbolic math package (I use MATLAB) and staring at the result for long enough, but this time it didn't.

So, I wonder: is there some automatic tool that helps with this kind of problem? Maybe something similar to AutoGraphiX?

On matrix norms

2013-02-09T15:38:56Z

It is standard to define an induced matrix norm $|||\cdot|||$ from a vector norm $||\cdot||$ in this way:

$|||A|||=\max_{x \neq 0}{\frac{||Ax||}{||x||}}$.

Suppose we define a different function of matrices this way:

$f(A)=\inf_{x \neq 0}{\frac{||Ax||}{||x||}}$.

Has $f(\cdot)$ been studied before? Does it have a standard name?

Ring-theoretic version of a matrix problem

2013-02-08T23:59:58Z

Problem #17 in Zhan's survey of open problems in matrix theory is the Li-Poon problem on writing a square real matrix as the linear combination of $k$ orthogonal matrices. They proved that it is possible to take $k=4$ for every square real matrix and asked if $k$ is the least possible such number.

I am wondering if there is a ring-theoretical version of this conjecture. This raises some even more basic questions:

What is the ring-theoretic equivalent of an orthogonal matrix?

And since an orthogonal matrix $O$ can be characterized as satisfying $OO^{T}=I$,

What is the ring-theoretic equivalent of the matrix transpose operation?

When is a Schur complement an $M$-matrix?

2012-05-11T00:07:57Z

Let $F=\begin{bmatrix}A & B \\ B^{T} & D\end{bmatrix}$ be symmetric and strictly diagonally dominant (thus an $H$-matrix). I also know that $B>0$ entrywise. What I am trying to show is that the Schur complements $F/A$ and $F/D$ are $M$-matrices. It doesn't hold in the general case but my actual matrix is quite special and I'm sure it holds for it, after checking numerous examples. Still, the raw calculations with the standard formulas are too painful. So, does anybody know of a general condition I can check?

Spectrum of a Laplacianized matrix

2013-02-07T17:34:20Z

Suppose that $A$ is a positive matrix and that we let $R$ be the diagonal matrix of $A$'s row-sums. What can be said about the spectrum of $R-A$? I am particularly interested in the largest eigenvalue of $R-A$.

Generalizations of Oppenheim's inequality

2012-08-28T18:13:12Z

The well-known Oppenheim inequality says that for two positive definite matrices $A,B$ it holds that $\det(A \circ B) \geq (\prod{a_{ii}})\det(B)$.

There has been a lot of beautiful work done extending it to cases when $A$ or $B$ or both of them are $M$-matrices or their inverses, or totally nonnegative.

My question is: do you know of other extensions, in which $A$ is non-symmetric in an "interesting" way?

Answer by Felix Goldberg for How to identify bridge nodes between nearly connected graph components in partitioned adjacency matrices?

2013-02-01T20:13:51Z

I think that in this very special case you can get the answer just by computing a minimum cut. If the two subgraphs are really dense and the bridges between them are few, then the minimum cut will be just the set of bridges.

Hamiltonian cycles in power-graphs

2013-01-16T12:45:00Z

I've stumbled across a short note from 1993 where a nice question was asked: Suppose you take a graph with vertices $\{1,2,\ldots,n\}$ and connect $i,j$ by an edge if and only if $i+j$ is a $k$th power of some number. Call this graph $G_{k}(n)$. The authors of the note found that $G_{2}(32)$ is Hamiltonian (and that $32$ is the first $n$ for which $G_{2}(n)$ is Hamiltonian). They conjectured that $G_{2}(n)$ is Hamiltonian for all $n \geq 32$.

I found no citations of this paper so I wonder if someone has attacked this question since.

UPDT: There is some discussion of the $k=3$ case here, from an "elementary" point of view.

Answer by Felix Goldberg for Which popular games are the most mathematical?

2013-01-29T11:41:21Z

I am a bit surprised that Dominion has not been mentioned yet. I am referring less to the gameplay itself rather than to the analyzes that people do in order to assess the "intrinsic worth" or "situational worth" (my terms) of a card or a strategy, using a rather complicated simulator. I perceive it as a kind of Monter Carlo analysis.

Pairwise balanced designs with $r=\lambda^{2}$

2013-01-28T15:14:13Z

A while ago I asked how to construct an infinite family of $(v,b,r,k,\lambda)$-designs satisfying $r=\lambda^{2}$ and got very good answers from Yuichiro Fujiwara and Ken W. Smith.

Now I'd like to up the ante and to generalize the question to $(r,\lambda)$-designs. Formally, we are talking here about a family $D$ of subsets of $\{1,2,\ldots,v\}$ such that:

(a) Each $i \in \{1,2,\ldots,v\}$ belongs to $r$ sets in $D$.

(b) Every two distinct $i,j \in \{1,2,\ldots,v\}$ belong together to $\lambda$ sets in $D$.

I am trying to find examples with $r=\lambda^{2}$, which is more difficult than in the case of $(v,k,\lambda)$ designs because this is more off the beaten path, so even stand-alone examples will be greatly appreciated.

P.S. As in the previous question, I require at least one pair of disjoint blocks, so most constructions based on symmetric designs will not apply here.

Answer by Felix Goldberg for Pairwise balanced designs with $r=\lambda^{2}$

2013-01-28T23:07:09Z

In the spirit of Yuichiro Fujuiwara's answer to my previous question, here's an approach that yields some examples: take a $(r,\lambda)$-design with $\lambda=1$ and a disjoint pair (aka a regular PBD $(v,K)$) and replicate the blocks $r$ times. I found a $(6,1)$-design in this paper by Lamken, Rees and Vanstone:

123 456 789 147 258 369

48 38 34 68 16 18

59 19 15 35 49 24

67 27 26 29 37 57

However, I'd love to see more examples of $(r,\lambda)$-designs with $r=\lambda^{2}$ that do not arise from this construction.

How random are random spanning trees?

2013-01-24T23:54:46Z

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices appear with the same frequency?

In other word: are some trees more likely than others to be spanning trees of a random graph?

Graphs with circulant distance matrices

2013-01-25T15:04:29Z

The cycle has this property. For instance, the distance matrix for a 6-cycle is:

$A=\begin{bmatrix}
0 & 1 & 2 & 3 & 2 & 1 \\ 1 & 0 & 1 & 2 & 3 & 2 \\ 2 & 1 & 0 & 1 & 2 & 3 \\ 3 & 2 & 1 & 0 & 1 & 2 \\ 2 & 3 & 2 & 1 & 0 & 1 \\ 1 & 2 & 3 & 2 & 1 & 0 \\ \end{bmatrix}$

The question is: is the cycle the only graph with this property?

Comment by Felix Goldberg

2013-05-13T19:33:35Z

Thanks, I'll try this!

Comment by Felix Goldberg

2013-05-02T16:10:21Z

Thanks, that makes a lot of sense. But what aboud the ear-decomposition? Can't we make it to good use somehow? I am willing even to settle for a non-polynomial but sane algorithm that will work in small cases.

Comment by Felix Goldberg

2013-04-30T08:31:15Z

Nice! What about a symmetric matrix, though? Does it change things if you stipulate symmetry?

Comment by Felix Goldberg

2013-04-30T08:16:07Z

I added "(0,1)" to the title. Hope you don't mind!

Comment by Felix Goldberg

2013-04-29T16:16:52Z

@quid an approximation might do, depending how good it is.

Comment by Felix Goldberg

2013-04-28T17:58:36Z

@Gerhard: By progress I mean the new results in hyperbolic polynomials that generalize van der Waerden's conjecture and a great deal of other results.

Comment by Felix Goldberg

2013-04-24T19:07:04Z

Actually, the JCT paper is freely available on the web. Just click the link and download it :) [Life has become just so much easier after Elsevier had capitulated...]

Comment by Felix Goldberg

2013-03-05T11:27:48Z

@AnthonyQuas: Yes, thanks.

Comment by Felix Goldberg

2013-03-05T11:27:36Z

@quid: Any way is interesting. Thanks for the edit!

Comment by Felix Goldberg

2013-03-04T11:20:52Z

@Suvrit: I added the statement of the theorem. But actually - sciderect have recently put all the old paper of many journals, including LAA, online for free - just try it :)

Comment by Felix Goldberg

2013-03-04T10:47:41Z

@DelioMugnolo: Indeed, and I indicated so in my answer. However, perhaps the OP could still derive some insights from it.

Comment by Felix Goldberg

2013-02-26T19:19:11Z

Sorry, I must be dense (and so uncoverable...) but why in 2 is there e countable cover?

Comment by Felix Goldberg

2013-02-23T11:02:46Z

Just to make sure - do you want to include linear algebra?

Comment by Felix Goldberg

2013-02-22T22:46:22Z

@GregMartin: Only the location (this time).

Comment by Felix Goldberg

2013-02-22T22:02:49Z

@nonlinearism: From my experience, research in industry may often be intellectually challenging, but it's rarely mathematical. Google, with pagerank may be a sort of outstanding counterexample, but I strongly suspect that even there the amount of time spent on actual mathematics is not that high. When working with data a lot of time and effort goes into "massaging" it and preparing it.