Completion of a partial integral matrix to a unimodular matrix

We first characterize submatrices of a unimodular integral matrix. We then prove that if n entries of an n × n partial integral matrix are prescribed and these n entries do not constitute a row or a column, then this matrix can be completed to a unimodular matrix. Consequently an n × n partial integral matrix with n − 1 prescribed entries can always be completed to a unimodular matrix.     

Structural properties and recognition of restricted and strongly unimodular matrices

A (0, ±1) matrix A is restricted unimodular if every matrix obtained from A by setting to zero any subset of its entries is totally unimodular. Restricted unimodular matrices are also known as matrices without odd cycles. They have been studied by Commoner and recently Yannakakis has given a polynomial algorithm to recognize when a matrix belongs to this class. A matrix A is strongly unimodular if any matrix obtained from A by setting at most one of its entries to zero is totally unimodular. Crama et al. have shown that (0,1) matrix A is strongly unimodular if and only if any basis of (A, 1) is triangular, whereI is an identity matrix of suitable dimensions. In this paper we give a very simple algorithm to test whether a matrix is restricted unimodular and we show that all strongly unimodular matrices can be obtained by composing restricted unimodular matrices with a simple operation. Partially supported by a New York University Research Challenge Fund Grant.     

Completion of partial matrices to contractions

An n-by-m partially specified complex matrix is called a partial contraction if every rectangular submatrix consisting entirely of specified entries is itself a contraction. Necessary and sufficient condition are given for the pattern of specified entries such that any n-by-m partial contraction with this pattern may be completed to a full n-by-m contraction.     

An algorithm for computing Jordan chains and inverting analytic matrix functions

We present an efficient algorithm for obtaining a canonical system of Jordan chains for an n × n regular analytic matrix function A(λ) that is singular at the origin. For any analytic vector function b(λ), we show that each term in the Laurent expansion of A(λ)⁻¹b(λ) may be obtained from the previous terms by solving an (n + d) × (n+d) linear system, where d is the order of the zero of det A(λ) at λ = 0. The matrix representing this linear system contains A(0) as a principal submatrix, which can be useful if A(0) is sparse. The last several iterations can be eliminated if left Jordan chains are computed in addition to right Jordan chains. The performance of the algorithm in floating point and exact (rational) arithmetic is reported for several test cases. The method is shown to be forward stable in floating point arithmetic.     

The elliptic matrix completion problem

Completions of partial elliptic matrices are studied. Given an undirected graph G, it is shown that every partial elliptic matrix with graph G can be completed to an elliptic matrix if and only if the maximal cliques of G are pairwise disjoint. Further, given a partial elliptic matrix A with undirected graph G, it is proved that if G is chordal and each specified principal submatrix defined by a pair of intersecting maximal cliques is nonsingular, then A can be completed to an elliptic matrix. Conversely, if G is nonchordal or if the regularity condition is relaxed, it is shown that there exist partial elliptic matrices which are not completable to an elliptic matrix. In the process we obtain several results concerning chordal graphs that may be of independent interest.     

On a generalization of the Evans Conjecture

The Evans Conjecture states that a partial Latin square of order n with at most n-1 entries can be completed. In this paper we generalize the Evans Conjecture by showing that a partial r-multi Latin square of order n with at most n-1 entries can be completed. Using this generalization, we confirm a case of a conjecture of Häggkvist.     

Completing partial latin squares

It is shown that if a partial latin square of order n with fewer than n entries has all its entries in no more than $\text{(n + 3)}\text{2}$ rows, then it can be completed. This extends previous results of both Lindner and Wells, but lately Wells has improved this to $\text{(n + 5)}\text{2}$. We show that the number $\text{(n + 3)}\text{2}$ is the best obtainable by the method of completing one row at a time without regard for completing future rows.     

Lattice-ordered matrix algebras containing positive cycles

It is shown that if a lattice-ordered n × n (n ≥ 2) matrix ring over a totally ordered integral domain or division ring containing a positive n-cycle, then it is isomorphic to the lattice-ordered n × n matrix ring with entrywise lattice order.     

Unitary equivalence to a complex symmetric matrix: An algorithm

We present a necessary and sufficient condition for a 3×3 matrix to be unitarily equivalent to a symmetric matrix with complex entries, and an algorithm whereby an arbitrary 3×3 matrix can be tested. This test generalizes to a necessary and sufficient condition that applies to almost every n×n matrix. The test is constructive in that it explicitly exhibits the unitary equivalence to a complex symmetric matrix.     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

Factorization of singular integer matrices

It is well known that a singular integer matrix can be factorized into a product of integer idempotent matrices. In this paper, we prove that every n  × n (n > 2) singular integer matrix can be written as a product of 3n + 1 integer idempotent matrices. This theorem has some application in the field of synthesizing VLSI arrays and systolic arrays.     

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.     

The spectra of some trees and bounds for the largest eigenvalue of any tree

Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n_k−j+1 and d_k−j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (n_k = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2 ? j ? k, while the diagonal entries are 0, …, 0, ±1, in the case of the adjacency matrix, and d₁, d₂, …, d_k−1, d_k ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree.     

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.     

On single and double Soules matrices

Until now the concept of a Soules basis matrix of sign patternN consisted of an orthogonal matrix R∈R^n,n, generated in a certain way from a positive n-vector, which has the property that for any diagonal matrix Λ = diag(λ₁, … , λ_n), with λ₁ ? ? ? λ_n ? 0, the symmetric matrix A = RΛR^T has nonnegative entries only. In the present paper we introduce the notion of a pair of double Soules basis matrices of sign patternN which is a pair of matrices (P, Q), each in R^n,n, which are not necessarily orthogonal and which are generated in a certain way from two positive vectors, but such that PQ^T = I and such that for any of the aforementioned diagonal matrices Λ, the matrix A = PΛQ^T (also) has nonnegative entries only. We investigate the interesting properties which such matrices A have.As a preamble to the above investigation we show that the iterates, , generated in the course of the QR-algorithm when it is applied to A = RΛR^T, where R is a Soules basis matrix of sign pattern N, are again symmetric matrices generated by the Soules basis matrices R_k of sign pattern N which are themselves modified as the algorithm progresses.Our work here extends earlier works by Soules and Elsner et al.     

Products of basic doubly stochastic matrices over a field

It is shown that if n?3, then every doubly stochastic matrix of order n over a field F is a product of doubly stochastic matrices with exactly two nonzero off- diagonal entries if and only if the characteristic of F is not 2 and F has more than three elements. A number of related results are also obtained.     

Solution of a tridiagonal operator equation

Let H be a separable Hilbert space with an orthonormal basis {e_n/n∈N}, T be a bounded tridiagonal operator on H and T_n be its truncation on span ({e₁, e₂, … , e_n}). We study the operator equation Tx = y through its finite dimensional truncations T_nxⁿ = y_n. It is shown that if and are bounded, then T is invertible and the solution of Tx = y can be obtained as a limit in the norm topology of the solutions of its finite dimensional truncations. This leads to uniform boundedness of the sequence . We also give sufficient conditions for the boundedness of and in terms of the entries of the matrix of T.     

On the completion of partial latin squares

In this paper a certain condition on partial latin squares is shown to be sufficient to guarantee that the partial square can be completed, namely, that it have fewer than n entries, and that at most $\text{[}\text{(n + 1)}\text{2}\text{]}$ of these lie off some line, where n is the order of the square. This is applied to establish that the Evans conjecture is true for n ? 8; i.e., that given a partial latin square of order n with fewer than n entries, n ? 8, the square can be completed. Finally, the results are viewed in a conjugate way to establish different conditions sufficient for the completion of a partial latin square.     

A combinatorial problem associated with nonograms

Associated with an m × n matrix with entries 0 or 1 are the m-vector of row sums and n-vector of column sums. In this article we study the set of all pairs of these row and column sums for fixed m and n. In particular, we give an algorithm for finding all such pairs for a given m and n.     

Wallman compactification and matrices of zeroes and ones

Let M be an m by n matrix (where m and n are any finite or infinite cardinals) such that the entries of M are 0's or 1's and M contains the zero row $\text{0}$ and the rows of M are closed under coordinatewise multiplication. We prove that M can be extended to an m by n′ ? n matrix M′ such that the entries of M′ are 0's or 1's and M′ contains the zero row 0?′ and the extension preserves the zero products. Moreover, the newly introduced columns (if any) are pairwise distinct. Furthermore, if E′ is any set of rows of M′ with the property that for every finite subset of rows r′_i of E′ there exists j < n′ such that r′_ij = 1, then every subset of rows of E′ has the same property. We rephrase this by saying that if E′ has the finite intersection property then E′ has a nonempty intersection. We also show (this time by Zorn's lemma) that there exists an extension of M with all the abovementioned properties such that the extension preserves products sums, complements and the newly introduced columns (if any) are pairwise distinct in a stricter sense. In effect, our result shows that the classical Wallman compactification theorem can be formulated purely combinatorially requiring no introduction of any topology on n.