Three dimensional line stochastic matrices and extreme points

Several properties of the extreme points of the convex set of three dimensional line stochastic matrices of order n are presented. The existence of many different classes of extremal configurations is established. These extremal matrices exhibit a large variety of patterns with some unexpected configurations. Latin squares of special types are used in some of the existence results. Furthermore, three questions raised by Brualdi and Csima are answered concerning the extreme points of three dimensional plane stochastic matrices of order n.     

Sur les génératrices extrémales de certains cônes de formes quadratiques doublement positives

We consider two classes of doubly positive quadratic forms on the space S of real symmetric matrices of order d ≥ 2, and prove that, for d = 2, these forms are the only extremal ones. This result fails for d ≥ 3.     

Order isomorphisms in cones and a characterization of duality for ellipsoids

We study order isomorphisms in finite-dimensional ordered vector spaces. We generalize theorems of Alexandrov, Zeeman, and Rothaus (valid for ??non-angular?? cones) to wide classes of cones, including in particular polyhedral cones, using a different and novel geometric method. We arrive at the following result: whenever the cone has more than n generic extremal vectors, an order isomorphism must be affine. In the remaining case, of precisely n extremal rays, the transform has a restricted diagonal form. To this end, we prove and use a new version of the well-known Fundamental theorem of affine geometry. We then apply our results to the cone of positive semi-definite matrices and get a characterization of its order isomorphisms. As a consequence, the polarity mapping is, up to a linear map, the only order-reversing isomorphism for ellipsoids.     

Properties of (0, 1)-matrices without certain configurations

We generalize results of Ryser on (0, 1)-matrices without triangles, 3 × 3 submatrices with row and column sums 2. The extremal case of matrices without triangles was previously studied by the author. Let the row intersection of row i and row j (i ≠ j) of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do not 0 otherwise. For matrices satisfying some conditions on forbidden configurations and column sums ? 2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. The extremal matrices with m rows and $\text{(}\text{m}\text{2}\text{)}$ distinct columns have a unique SDR of pairs of rows with 1's. A triangle bordered with a column of 0's and its (0, 1)-complement are also considered as forbidden configurations. Similar results are obtained and the extremal matrices are closely related to the extremal matrices without triangles.     

Submatrices of non-tree-realizable distance matrices

We deal with distance matrices of real (this means, not necessarily integer) numbers. It is known that a distance matrix D of order n is tree-realizable if and only if all its principal submatrices of order 4 are tree-realizable. We discuss bounds for the number, denoted Q_i(D), of non-tree-realizable principal submatrices of order i ? 4 of a non-tree-realizable distance matrix D of order n?i, and we construct some distance matrices which meet extremal conditions on Q_i(D). Our starting point is a proof that a non-tree-realizable distance matrix of order 5 has at least two non-tree-realizable principal submatrices of order 4. Optimal realizations (by graphs with circuits) of distance matrices which are not tree-realizable are not yet as well known as optimal realizations which are trees. Using as starting point the optimal realization of the (arbitrary) distance matrix of order 4, we investigate optimal realizations of non-tree-realizable distance matrices with the minimum number of non-tree-realizable principal submatrices of order 4.     

Equalities and inequalities for inertias of hermitian matrices with applications

The inertia of a Hermitian matrix is defined to be a triplet composed of the numbers of the positive, negative and zero eigenvalues of the matrix counted with multiplicities, respectively. In this paper, we show some basic formulas for inertias of 2×2 block Hermitian matrices. From these formulas, we derive various equalities and inequalities for inertias of sums, parallel sums, products of Hermitian matrices, submatrices in block Hermitian matrices, differences of outer inverses of Hermitian matrices. As applications, we derive the extremal inertias of the linear matrix expression A-BXB^∗ with respect to a variable Hermitian matrix X. In addition, we give some results on the extremal inertias of Hermitian solutions to the matrix equation AX=B, as well as the extremal inertias of a partial block Hermitian matrix.     

Additive representation of symmetric inverse M-matrices and potentials

In this article we characterize the closed cones respectively generated by the symmetric inverse M-matrices and by the inverses of symmetric row diagonally dominant M-matrices. We show the latter has a finite number of extremal rays, while the former has infinitely many extremal rays. As a consequence we prove that every potential is the sum of ultrametric matrices.     

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.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

Precise asymptotics for beta ensembles

We consider the extremal (largest and smallest) eigenvalues of random matrices in the β-Hermite and β-Laguerre ensembles. Using the general β Tracy-Widom law together with Ledoux and Rider’s small deviation inequalities for β-ensembles, we obtain some precise asymptotic results in both settings. This complements Su’s results for the largest eigenvalue of Gaussian and Laguerre unitary ensembles.     

Properties of (0, 1)-matrices with no triangles

We study (0, 1)-matrices which contain no triangles (submatrices of order 3 with row and column sums 2) previously studied by Ryser. Let the row intersection of row i and row j of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do and a zero otherwise. For matrices with no triangles, columns sums ?2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. We then study the extremal (0, 1)-matrices with no triangles, column sums ?2, distinct columns, i.e., those of size mx(^m₂). The number of columns of column sum l is m ? l + 1 and they form a (l ? 1)-tree. The ((^m₂)) columns have a unique SDR of pairs of rows with 1's. Also, these matrices have a fascinating inductive buildup. We finish with an algorithm for constructing these matrices.     

A graph theoretic upper bound on the permanent of a nonnegative integer matrix. II. The extremal case

Matrices A for which the upper bound per(A)?1+min{Π(c_i?1), Π(r_i?1)} holds with equality are characterized. Cases where the bound is achieved correspond to multigraphs with the property that there exists a unique path from any vertex to any disjoint cycle union. This occurs precisely when some multigraph associated with A has the mastercycle property: all cycles thread all branchpoints in the same circular order. Such multigraphs may also be characterized as a circular concatenation of certain acyclic multigraphs, each having a unique source and sink. This analysis yields two normal forms for the extremal matrices, one based on a nested block decomposition, and another based on an overlapping block decomposition. The extremal cases are invariant under contractions, yielding another characterization.     

An algorithm for finding extremal polytope norms of matrix families

In this paper the problem of the computation of the joint spectral radius of a finite set of matrices is considered. We present an algorithm which, under some suitable assumptions, is able to check if a certain product in the multiplicative semigroup is spectrum maximizing. The algorithm proceeds by attempting to construct a suitable extremal norm for the family, namely a complex polytope norm. As examples for testing our technique, we first consider the set of two 2-dimensional matrices recently analyzed by Blondel, Nesterov and Theys to disprove the finiteness conjecture, and then a set of 3-dimensional matrices arising in the zero-stability analysis of the 4-step BDF formula for ordinary differential equations.     

Extremal eigenvalue intervals of symmetric tridiagonal interval matrices

Computing the extremal eigenvalue bounds of interval matrices is non‐deterministic polynomial‐time (NP)‐hard. We investigate bounds on real eigenvalues of real symmetric tridiagonal interval matrices and prove that for a given real symmetric tridiagonal interval matrices, we can achieve its exact range of the smallest and largest eigenvalues just by computing extremal eigenvalues of four symmetric tridiagonal matrices.     

On the exact Markov inequality for k-monotone polynomials in uniform and L 1-norms

We consider the classical extremal problem of estimating norms of higher order derivatives of algebraic polynomials when their norms are given. The corresponding extremal problem for general polynomials in uniform norm was solved by A. A. Markov, while Bernstein found the exact constant in the Markov inequality for monotone polynomials. In this note we give Markov-type inequalities for higher order derivatives in the general class of k-monotone polynomials. In particular, in case of first derivative we find the exact solution of this extremal problem in both uniform and L ₁-norms. This exact solution is given in terms of the largest zeros of certain Jacobi polynomials.     

Some inequalities for multidimensional (0,1)- matrices

Can there exist a (0,1)-matrix of order n and dimension d, such that the sum on any e-dimensional hyperplane of the matrix is a fixed number r? The answer to this question is of importance both for the construction of incomplete block designs and for the investigation of extremal points in the convex sets of multidimensional stochastic matrices. Some necessary conditions that must be fulfilled by the parameters n, d, e, and r are deduced in this paper.     

Type I neighbors of extremal type II codes of length 40 derived from Hadamard matrices

Self-dual codes C₁,C₂ of length n are called neighbors to each other if C₁∩C₂ has dimension (n/2−1). With the aide of a computer, we search for Type I neighbors of some extremal Type II codes of length 40 which are derived from Hadamard matrices of order 20. As a result, we get extremal Type I neighbors (up to equivalence) that have weight enumerators W₄₀(y)=1+(125+16β)y⁸+⋯ with β=0,…,4,6,8,10.a     

Tail dependence between order statistics

In this work, we introduce the s,k-extremal coefficients for studying the tail dependence between the s-th lower and k-th upper order statistics of a normalized random vector. If its margins have tail dependence then so do their order statistics, with the strength of bivariate tail dependence decreasing as two order statistics become farther apart. Some general properties are derived for these dependence measures which can be expressed via copulas of random vectors. Its relations with other extremal dependence measures used in the literature are discussed, such as multivariate tail dependence coefficients, the coefficient η of tail dependence, coefficients based on tail dependence functions, the extremal coefficient ?, the multivariate extremal index and an extremal coefficient for min-stable distributions. Several examples are presented to illustrate the results, including multivariate exponential and multivariate Gumbel distributions widely used in applications.     

Extremal Trigonometric and Power Polynomials in Several Variables

We study extremal nonnegative polynomials in several variables. Our approach makes substantial use of block Toeplitz matrices. Note that the blocks of these matrices are themselves Toeplitz matrices.     

A note on the perturbation of positive matrices by normal and unitary matrices

In a recent paper, Neumann and Sze considered for an n × n nonnegative matrix A, the minimization and maximization of ρ(A + S), the spectral radius of (A + S), as S ranges over all the doubly stochastic matrices. They showed that both extremal values are always attained at an n × n permutation matrix. As a permutation matrix is a particular case of a normal matrix whose spectral radius is 1, we consider here, for positive matrices A such that (A + N) is a nonnegative matrix, for all normal matrices N whose spectral radius is 1, the minimization and maximization problems of ρ(A + N) as N ranges over all such matrices. We show that the extremal values always occur at an n × n real unitary matrix. We compare our results with a less recent work of Han, Neumann, and Tastsomeros in which the maximum value of ρ(A + X) over all n × n real matrices X of Frobenius norm was sought.