The critical exponent conjecture for powers of doubly nonnegative matrices

Doubly nonnegative matrices arise naturally in many setting including Markov random fields (positively banded graphical models) and in the convergence analysis of Markov chains. In this short note, we settle a recent conjecture by C.R. Johnson et al. [Charles R. Johnson, Brian Lins, Olivia Walch, The critical exponent for continuous conventional powers of doubly nonnegative matrices, Linear Algebra Appl. 435 (9) (2011) 2175–2182] by proving that the critical exponent beyond which all continuous conventional powers of n-by-n   doubly nonnegative matrices are doubly nonnegative is exactly n−2$n-2$. We show that the conjecture follows immediately by applying a general characterization from the literature. We prove a stronger form of the conjecture by classifying all powers preserving doubly nonnegative matrices, and proceed to generalize the conjecture for broad classes of functions. We also provide different approaches for settling the original conjecture.     

Long-wave instabilities and saturation in thin film equations

Hocherman and Rosenau conjectured that long-wave unstable Cahn-Hilliard-type interface models develop finite-time singularities when the nonlinearity in the destabilizing term grows faster at large amplitudes than the nonlinearity in the stabilizing term (Phys.˜ D 67, 1993, pp. 113–125). We consider this conjecture for a class of equations, often used to model thin films in a lubrication context, by showing that if the solutions are uniformly bounded above or below (e.g., are nonnegative), then the destabilizing term can be stronger than previously conjectured yet the solution still remains globally bounded. For example, they conjecture that for the long-wave unstable equation m > n leads to blowup. Using a conservation-of-volume constraint for the case m > n > 0, we conjecture a different critical exponent for possible singularities of nonnegative solutions. We prove that nonlinearities with exponents below the conjectured critical exponent yield globally bounded solutions. Specifically, for the above equation, solutions are bounded if m < n + 2. The bound is proved using energy methods and is then used to prove the existence of nonnegative weak solutions in the sense of distributions. We present preliminary numerical evidence suggesting that m ≥ n + 2 can allow blowup. © 1998 John Wiley & Sons, Inc.     

On a conjecture about the exponent set of primitive matrices

M. Lewin and Y. Vitek conjecture [7] that every integer $\text{?[}\text{(n>}{}^2\text{?2n+2)}\text{2}\text{]+1}$ is an exponent of some n×n primitive matrix. In this paper, we prove three results related to Lewin and Vitek's conjecture: (1) Every integer $\text{?[}\text{(n}{}^2\text{?2n+2)}\text{4}\text{]+1}$ is an exponent of some n×n primitive matrix. (2) The conjecture is true when n is sufficiently large. (3) We give a counterexample to show that the conjecture is not true in the case when n=11.     

Latin trades on three or four rows

Latin trades are closely related to the problem of critical sets in Latin squares. We denote the cardinality of the smallest critical set in any Latin square of order n by scs(n). A consideration of Latin trades which consist of just two columns, two rows, or two elements establishes that scs(n)?n-1. We conjecture that a consideration of Latin trades on four rows may establish that scs(n)?2n-4. We look at various attempts to prove a conjecture of Cavenagh about such trades. The conjecture is proven computationally for values of n less than or equal to 9. In particular, we look at Latin squares based on the group table of Z_n for small n and trades in three consecutive rows of such Latin squares.     

Finite time blow up for critical wave equations in high dimensions

We prove that solutions to the critical wave equation (1.1) with dimension n?4 can not be global if the initial values are positive somewhere and nonnegative. This completes the solution to the famous Strauss conjecture about semilinear wave equations of the form . The rest of the cases, the lower-dimensional case n?3, and the sub or super critical cases were settled many years earlier by the work of several authors.     

The critical Lazer-McKenna conjecture in low dimensions

We study a problem related to the Lazer-McKenna conjecture in the critical case. Recent results on this conjecture in this case have been obtained in dimensions n?6. We prove here that the situation is drastically different in lower dimensions.     

Highly connected monochromatic subgraphs

We conjecture that for n>4(k-1) every 2-coloring of the edges of the complete graph K_n contains a k-connected monochromatic subgraph with at least n-2(k-1) vertices. This conjecture, if true, is best possible. Here we prove it for k=2, and show how to reduce it to the case n<7k-6. We prove the following result as well: for n>16k every 2-colored K_n contains a k-connected monochromatic subgraph with at least n-12k vertices.     

Matrices satisfying the van der Waerden conjecture

It is shown here that any n×n doubly stochastic matrix whose numerical range lies in the sector from -π/2n to π/2n satisfies the van der Waerden conjecture.     

Asymptotics of products of nonnegative random matrices

Asymptotic properties of products of random matrices ξ _k = X _k …X ₁ as k → ∞ are analyzed. All product terms X _i are independent and identically distributed on a finite set of nonnegative matrices A = {A ₁, …, A _m }. We prove that if A is irreducible, then all nonzero entries of the matrix ξ _k almost surely have the same asymptotic growth exponent as k→∞, which is equal to the largest Lyapunov exponent λ(A). This generalizes previously known results on products of nonnegative random matrices. In particular, this removes all additional “nonsparsity” assumptions on matrices imposed in the literature.We also extend this result to reducible families. As a corollary, we prove that Cohen’s conjecture (on the asymptotics of the spectral radius of products of random matrices) is true in case of nonnegative matrices.     

On the exponent of a primitive digraph

We characterize the equality case of the upper bound $\text{γ(D) ? n + s(n ? 2)}$ for the exponent of a primitive digraph in the case s ? 2, where n is the number of the vertices of the digraph D and s is the length of the shortest elementary circuit of D. We also answer a question about the equality case when s = 1. The exponent of an n × n primitive nonnegative matrix A is the same as the exponent of the associated digraph D(A) of A. So every theorem in this paper can be translated into a theorem about nonnegative matrices.     

A conjecture on convex polyhedra

We select a class of pyramids of a particular shape and propose a conjecture that precisely these pyramids are of greatest surface area among the closed convex polyhedra having evenly many vertices and the unit geodesic diameter. We describe the geometry of these pyramids. The confirmation of our conjecture will solve the “doubly covered disk” problem of Alexandrov. Through a connection with Reuleaux polygons we prove that on the plane the convex n-gon of unit diameter, for odd n, has greatest area when it is regular, whereas this is not so for even n.     

Matrices with maximum kth local exponent in the class of doubly symmetric primitive matrices

Let A be a primitive matrix of order n, and let k be an integer with 1?k?n. The kth local exponent of A, is the smallest power of A for which there are k rows with no zero entry. We have recently obtained the maximum value for the kth local exponent of doubly symmetric primitive matrices of order n with 1?k?n. In this paper, we use the graph theoretical method to give a complete characterization of those doubly symmetric primitive matrices whose kth local exponent actually attain the maximum value.     

Lagrangian 4-planes in holomorphic symplectic varieties of K3[4]-type

We classify the cohomology classes of Lagrangian 4-planes ?⁴ in a smooth manifold X deformation equivalent to a Hilbert scheme of four points on a K3 surface, up to the monodromy action. Classically, the Mori cone of effective curves on a K3 surface S is generated by nonnegative classes C, for which (C, C) ≥ 0, and nodal classes C, for which (C, C) = ?2; Hassett and Tschinkel conjecture that the Mori cone of a holomorphic symplectic variety X is similarly controlled by “nodal” classes C such that (C, C) = ?γ, for (·,·) now the Beauville-Bogomolov form, where γ classifies the geometry of the extremal contraction associated to C. In particular, they conjecture that for X deformation equivalent to a Hilbert scheme of n points on a K3 surface, the class C = ? of a line in a smooth Lagrangian n-plane ? ⁿ must satisfy (?,?) = ?(n + 3)/2. We prove the conjecture for n = 4 by computing the ring of monodromy invariants on X, and showing there is a unique monodromy orbit of Lagrangian 4-planes.     

Wielandt type theorem for Cartesian product of digraphs

We show that mn-1 is an upper bound of the exponent of the Cartesian product D×E of two digraphs D and E on m,n vertices, respectively and we prove our upper bound is extremal when (m,n)=1. We also find all D and E when the exponent of D×E is mn-1. In addition, when m=n, we prove that the extremal upper bound of exp(D×E) is n²-n+1 and only the Cartesian product, Z_n×W_n, of the directed cycle and Wielandt digraph has exponent equals to this bound.     

EXISTENCE AND NONEXISTENCE OF GLOBAL POSITIVE SOLUTIONS FOR DEGENERATE PARABOLIC EQUATIONS IN EXTERIOR DOMAINS

This article deals with the degenerate parabolic equations in exterior domains and with inhomogeneous Dirichlet boundary conditions. We obtain that pc = (σ+m)n/(n-σ-2) is its critical exponent provided max{-1, [(1-m)n-2]/(n+1)} σ n-2. This critical exponent is not the same as that for the corresponding equations with the boundary value 0, but is more closely tied to the critical exponent of the elliptic type degenerate equations. Furthermore, we demonstrate that if max{1, σ + m} p ≤ pc, then every positive solution of the equations blows up in finite time; whereas for ppc, the equations admit global positive solutions for some boundary values and initial data. Meantime, we also demonstrate that its positive solutions blow up in finite time provided n ≤σ+2.     

Tactical decompositions and orbits of projective groups

We consider decompositions of the incidence structure of points and lines of PG(n, q) (n?3) with equally many point and line classes. Such a decomposition, if line-tactical, must also be point-tactical. (This holds more generally in any 2-design.) We conjecture that such a tactical decomposition with more than one class has either a singleton point class, or just two point classes, one of which is a hyperplane. Using the previously mentioned result, we reduce the conjecture to the case n=3, and prove it when q²+q+1 is prime and for very small values of q. The truth of the conjecture would imply that an irreducible collineation group of PG(n, q) (n?3) with equally many point and line orbits is line-transitive (and hence known).     

On linear forbidden submatrices

In this paper we study the extremal problem of finding how many 1 entries an n by n 0-1 matrix can have if it does not contain certain forbidden patterns as submatrices. We call the number of 1 entries of a 0-1 matrix its weight. The extremal function of a pattern is the maximum weight of an n by n 0-1 matrix that does not contain this pattern as a submatrix. We call a pattern (a 0-1 matrix) linear if its extremal function is O(n). Our main results are modest steps towards the elusive goal of characterizing linear patterns. We find novel ways to generate new linear patterns from known ones and use this to prove the linearity of some patterns. We also find the first minimal non-linear pattern of weight above 4. We also propose an infinite sequence of patterns that we conjecture to be minimal non-linear but have Ω(nlogn) as their extremal function. We prove a weaker statement only, namely that there are infinitely many minimal not quasi-linear patterns among the submatrices of these matrices. For the definition of these terms see below.     

On a conjecture of Butler and Graham

Motivated by a hat guessing problem proposed by Iwasawa, Butler and Graham made the following conjecture on the existence of a certain way of marking the coordinate lines in [k] ⁿ : there exists a way to mark one point on each coordinate line in [k] ⁿ , so that every point in [k] ⁿ is marked exactly a or b times as long as the parameters (a, b, n, k) satisfies that there are nonnegative integers s and t such that s + t = k ⁿ and as + bt = nk ^n?1. In this paper we prove this conjecture for any prime number k. Moreover, we prove the conjecture for the case when a = 0 for general k.     

Heuristics for exact nonnegative matrix factorization

The exact nonnegative matrix factorization (exact NMF) problem is the following: given an m-by-n nonnegative matrix X and a factorization rank r, find, if possible, an m-by-r nonnegative matrix W and an r-by-n nonnegative matrix H such that \(X = WH\). In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show empirically that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic n-gons and conjecture the exact value of (i) the extension complexity of regular n-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope.     

On a conjecture about the eigenvalues of doubly stochastic matrices

According to a long standing conjecture, the geometric location of eigenvalues of doubly stochastic matrices of order n is exactly the union of regular k-gons anchored at 1 in the unit disc for 2 ≤ k ≤ n. It is easy to verify this fact for n?=?2,?3. But, for n?≥?4, it has been an open question. We show that this conjecture is wrong for n?=?5.