A catalog of minimally nonideal matrices

This paper describes a backtracking algorithm for the enumeration of nonisomorphic minimally nonideal (n ×n) matrices that are not degenerate projective planes. The application of this algorithm forn 12 yielded 20 such matrices, adding 5 matrices to the 15 previously known. For greater dimensions,n = 14 andn = 17, 13 new matrices are given. For nonsquare matrices, 38 new minimally nonindeal matrices are described.Research supported by FNRS grant. Switzerland, while visiting Carnegie Mellon University, Pittsburgh, PA 15213.     

On the eigenvalues of double band matrices

We consider matrices containing two diagonal bands of positive entries. We show that all eigenvalues of such matrices are of the form rζ, where r is a nonnegative real number and ζ is a pth root of unity, where p is the period of the matrix, which is computed from the distance between the bands. We also present a problem in the asymptotics of spectra in which such double band matrices are perturbed by banded matrices.     

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 the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

Contractions with rank one defect operators and truncated CMV matrices

The main issue we address in the present paper are the new models for completely nonunitary contractions with rank one defect operators acting on some Hilbert space of dimension N?∞. These models complement nicely the well-known models of Livšic and Sz.-Nagy-Foias. We show that each such operator acting on some finite-dimensional (respectively, separable infinite-dimensional Hilbert space) is unitarily equivalent to some finite (respectively semi-infinite) truncated CMV matrix obtained from the “full” CMV matrix by deleting the first row and the first column, and acting in CN (respectively ?²(N)). This result can be viewed as a nonunitary version of the famous characterization of unitary operators with a simple spectrum due to Cantero, Moral and Velázquez, as well as an analog for contraction operators of the result from [Yu. Arlinski?, E. Tsekanovski?, Non-self-adjoint Jacobi matrices with a rank-one imaginary part, J. Funct. Anal. 241 (2006) 383-438] concerning dissipative non-self-adjoint operators with a rank one imaginary part. It is shown that another functional model for contractions with rank one defect operators takes the form of the compression f(ζ)→PK(ζf(ζ)) on the Hilbert space L²(T,dμ) with a probability measure μ onto the subspace K=L²(T,dμ)?C. The relationship between characteristic functions of sub-matrices of the truncated CMV matrix with rank one defect operators and the corresponding Schur iterates is established. We develop direct and inverse spectral analysis for finite and semi-infinite truncated CMV matrices. In particular, we study the problem of reconstruction of such matrices from their spectrum or the mixed spectral data involving Schur parameters. It is pointed out that if the mixed spectral data contains zero eigenvalue, then no solution, unique solution or infinitely many solutions may occur in the inverse problem for truncated CMV matrices. The uniqueness theorem for recovered truncated CMV matrix from the given mixed spectral data is established. In this part the paper is closely related to the results of Hochstadt and Gesztesy-Simon obtained for finite self-adjoint Jacobi matrices.     

The DJL Conjecture for CP Matrices over Special Inclines

Drew, Johnson, and Loewy conjectured that for n ≥ 4, the CP-rank of every n × n completely positive real matrix is at most [n²/4]. While this conjecture has recently been disproved for completely positive real matrices, we show that this conjecture is true for n × n completely positive matrices over certain special types of inclines. In addition, we prove an incline version of Markham's theorems which gives sufficient conditions for completely positive matrices over special inclines to have triangular factorizations.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

Symmetric Weighing Matrices Constructed using Group Matrices

A weighing matrix of order n and weight m² is a square matrix M of order n with entries from {-1,0,+1} such that MM^T=m²I where I is the identity matrix of order n. If M is a group matrix constructed using a group of order n, M is called a group weighing matrix. Recently, group weighing matrices were studied intensively, especially when the groups are cyclic and abelian. In this paper, we study the abelian group weighing matrices that are symmetric, i.e.M^T=M. Some new examples are found. Also we obtain a few exponent bounds on abelian groups that admit symmetric group weighing matrices. In particular, we prove that there is no symmetric abelian group weighing matrices of order 2p^r and weight p² where p is a prime and p≥ 5.Communicated by: K.T. Arasu     

Hadamard Matrices Modulo p and Small Modular Hadamard Matrices

We use modular symmetric designs to study the existence of Hadamard matrices modulo certain primes. We solve the 7‐modular and 11‐modular versions of the Hadamard conjecture for all but a finite number of cases. In doing so, we state a conjectural sufficient condition for the existence of a p‐modular Hadamard matrix for all but finitely many cases. When 2 is a primitive root of a prime p, we conditionally solve this conjecture and therefore the p‐modular version of the Hadamard conjecture for all but finitely many cases when , and prove a weaker result for . Finally, we look at constraints on the existence of m‐modular Hadamard matrices when the size of the matrix is small compared to m.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

Symmetric matrices related to the Mertens function

In this paper, we explore a family of congruences over N^∗ from which one builds a sequence of symmetric matrices related to the Mertens function. From the results of numerical experiments, we formulate a conjecture about the growth of the quadratic norm of these matrices, which implies the Riemann hypothesis. This suggests that matrix analysis methods may come to play a more important role in this classical and difficult problem.     

Conley's spectral sequence via the sweeping algorithm

In this article we consider a spectral sequence (Er,dr) associated to a filtered Morse-Conley chain complex (C,Δ), where Δ is a connection matrix. The underlying motivation is to understand connection matrices under continuation. We show how the spectral sequence is completely determined by a family of connection matrices. This family is obtained by a sweeping algorithm for Δ over fields F as well as over Z. This algorithm constructs a sequence of similar matrices Δ⁰=Δ,Δ¹,… , where each matrix is related to the others via a change-of-basis matrix. Each matrix Δr over F (resp., over Z) determines the vector space (resp., Z-module) Er and the differential dr. We also prove the integrality of the final matrix ΔR produced by the sweeping algorithm over Z which is quite surprising, mainly because the intermediate matrices in the process may not have this property. Several other properties of the change-of-basis matrices as well as the intermediate matrices Δr are obtained.     

Perfect zero–one matrices

A zero–one matrix is called perfect if the polytope of the associated set packing problem has integral vertices only. By this definition, all totally unimodular zero–one matrices are perfect. In this paper we give a characterization of perfect zero–one matrices in terms offorbidden submatrices. Perfect zero–one matrices are closely related to perfect graphs and constitute a generalization of balanced matrices as introduced by C. Berge. Furthermore, the results obtained here bear on an unsolved problem in graph theory, the strong perfect graph conjecture, also due to C. Berge.     

A companion matrix approach to the study of zeros and critical points of a polynomial

In this paper, we introduce a new type of companion matrices, namely, D-companion matrices. By using these D-companion matrices, we are able to apply matrix theory directly to study the geometrical relation between the zeros and critical points of a polynomial. In fact, this new approach will allow us to prove quite a number of new as well as known results on this topic. For example, we prove some results on the majorization of the critical points of a polynomial by its zeros. In particular, we give a different proof of a recent result of Gerhard Schmeisser on this topic. The same method allows us to prove a higher order Schoenberg-type conjecture proposed by M.G. de Bruin and A. Sharma.     

On a number of poisson matrices in Bang-Bang representations for 3 × 3 embeddable matrices

We give a counterexample to the Strong Bang-Bang Conjecture according to which any 3 × 3 embeddable matrix can be expressed as a product of six Poisson matrices. We exhibit a 3 × 3 embeddable matrix which can be expressed as a product of seven but not six Poisson matrices. We show that an embeddable 3 × 3 matrix P with det $\text{P ≥}\text{1}\text{8}$ can be expressed as a product of at most six Poisson matrices and give necessary and sufficient conditions for a 3 × 3 stochastic matrix P with det $\text{P ≥}\text{1}\text{8}$ to be embeddable. For an embeddable 3 × 3 matrix P with det $\text{P <}\text{1}\text{8}$ we give a new bound for the number of Poisson matrices in its Bang-Bang representation.     

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

Transforming an error-tolerant separable matrix to an error-tolerant disjunct matrix

Recently, Chen and Hwang [H.B. Chen, F.K. Hwang, Exploring the missing link among d-separable, -separable and d-disjunct matrices, Discrete Applied Mathematics 133 (2007) 662-664] provided a method for transforming a separable matrix to a disjunct matrix. In [D.Z. Du, F.K. Hwang, Pooling Designs and Nonadaptive Group Testing — Important Tools for DNA Sequencing, World Scientific, 2006], Du and Hwang attempted to extend this result to its error-tolerant version; unfortunately, they gave an incorrect extension. This note gives a solution to this problem.     

A Newton-based method for the calculation of the distance to instability

In this paper, a new fast algorithm for the computation of the distance of a stable matrix to the unstable matrices is provided. The method uses Newton’s method to find a two-dimensional Jordan block corresponding to a pure imaginary eigenvalue in a certain two-parameter Hamiltonian eigenvalue problem introduced by Byers [R. Byers, A bisection method for measuring the distance of a stable matrix to the unstable matrices, SIAM J. Sci. Statist. Comput. 9 (1988) 875-881]. This local method is augmented by a test step, previously used by other authors, to produce a global method. Numerical results are presented for several examples and comparison is made with the methods of Boyd and Balakrishnan [S. Boyd, V. Balakrishnan, A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its L_∞-norm, Systems Control Lett. 15 (1990) 1-7] and He and Watson [C. He, G.A. Watson, An algorithm for computing the distance to instability, SIAM J. Matrix Anal. Appl. 20 (1999) 101-116].     

The Hankel pencil conjecture

The Toeplitz pencil conjecture stated in [W. Schmale, P.K. Sharma, Problem 30-3: singularity of a toeplitz matrix, IMAGE 30 (2003); W. Schmale, P.K. Sharma, Cyclizable matrix pairs over and a conjecture on toeplitz pencils, Linear Algebra Appl. 389 (2004) 33-42] is equivalent to a conjecture for n×n Hankel pencils of the form H_n(x)=(c_i+j-n+1), where c₀=x is an indeterminate, c_l=0 for l<0, and for l1. In this paper it is shown to be implied by another conjecture, which we call the root conjecture. The root conjecture asserts a strong relationship between the roots of certain submaximal minors of H_n(x) specialized to have c₁=c₂=1. We give explicit formulae in the c_i for these minors and prove the root conjecture for minors m_nn,m_n-1,n of degree 6. This implies the Hankel Pencil conjecture for matrices up to size 8×8. The main tools involved are a partial parametrization of the set of solutions of systems of polynomial equations that are both homogeneous and index sum homogeneous, and use of the Sylvester identity for matrices.