Determinants of nonprincipal submatrices of positive semidefinite matrices

We compute here the maximum value of the modulus of the determinant of an m×m nonprincipal submatrix of an n×n positive semidefinite matrix A, in terms of m, the eigenvalues of A, and cardinality k of the set of common row and column indices of this submatrix.     

On normal matrices with normal principal submatrices

Let A be a normal n×n matrix. This paper discusses in detail under what conditions and in what way A can be dilated to a normal matrix of order n+1 or n+2. Bibliography: 4 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 63–94. Translated by Kh. D. Ikramov.     

On inversion of hermitian block toeplitz matrices

A formula for the inverse of a hermitian block Toeplitz matrix via solutions of two block equations(instead of four in the general case) is given.     

On the ranks of principal submatrices of diagonalizable matrices

As is well known, the rank of a diagonalizable complex matrix can be characterized as the maximum order of the nonzero principal minors of this matrix. The standard proof of this fact is based on representing the coefficients of the characteristic polynomial as the (alternating) sums of all the principal minors of appropriate order. We show that in the case of normal matrices, one can give a simple direct proof, not relying on those representations. Bibliography: 2 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 359, 2008, pp. 42–44.     

Rank-deficient submatrices of Fourier matrices

We consider the maximal rank-deficient submatrices of Fourier matrices with order a power of a prime number. We do this by considering a hierarchical subdivision of these matrices into low rank blocks. We also explore some connections with the fast Fourier transform (FFT), and with an uncertainty principle for Fourier transforms over finite Abelian groups.     

On 0-1 matrices and small excluded submatrices

We say that a 0-1 matrix A avoids another 0-1 matrix (pattern) P if no matrix P^′ obtained from P by increasing some of the entries is a submatrix of A. Following the lead of (SIAM J. Discrete Math. 4 (1991) 17-27; J. Combin. Theory Ser. A 55 (1990) 316-320; Discrete Math. 103 (1992) 233-251) and other papers we investigate n by n 0-1 matrices avoiding a pattern P and the maximal number ex(n,P) of 1 entries they can have. Finishing the work of [8] we find the order of magnitude of ex(n,P) for all patterns P with four 1 entries. We also investigate certain collections of excluded patterns. These sets often yield interesting extremal functions different from the functions obtained from any one of the patterns considered.     

Conjugate-normal matrices with conjugate-normal submatrices

In studying the reduction of a complex n × n matrix A to its Hessenberg form by the Arnoldi algorithm, T. Huckle discovered that an irreducible Hessenberg normal matrix with a normal leading principal m × m submatrix, where 1 < m < n, actually is tridiagonal. We prove a similar assertion for the conjugate-normal matrices, which play the same role in the theory of unitary congruences as the conventional normal matrices in the theory of unitary similarities. This fact is stated as a purely matrix-theoretic theorem, without any reference to Arnoldi-like algorithms. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 346, 2007, pp. 21–25.     

Diagonal norm hermitian matrices

If v is a norm on $\text{C}$ⁿ, let H(v) denote the set of all norm-Hermitians in $\text{C}$ⁿⁿ. Let S be a subset of the set of real diagonal matrices D. Then there exists a norm v such that S=H(v) (or S = H(v)∩D) if and only if S contains the identity and S is a subspace of D with a basis consisting of rational vectors. As a corollary, it is shown that, for a diagonable matrix h with distinct eigenvalues λ₁,…, λ_r, r?n, there is a norm v such that h ∈ H(v), but h^s?H(v), for some integer s, if and only if λ₂–λ₁,…, λ_r–λ₁ are linearly dependent over the rationals. It is also shown that the set of all norms v, for which H(v) consists of all real multiples of the identity, is an open, dense subset, in a natural metric, of the set of all norms.     

Arbitrary perturbations of hermitian matrices

Kahan's results on the perturbation of the eigenvalues of a hermitian matrix A affected by an arbitrary perturbation A+X are improved in two ways. Better constants are given, and it is shown that the estimates do not depend on the size of A, but only on the size of the clusters of eigenvalues of A, relative to the euclidean norm of X.     

On classes of matrices containing M-matrices and hermitian positive semidefinite matrices

Two new classes of matrices are introduced, containing hermitian positive semi-definite matrices and M-matrices. The relation to other well-known classes such as ω and τ-matrices and weakly sign symmetric matrices is examined, and invariance properties are shown.     

The eigenvalue spreads of a hermitian matrix and its principal submatrices

Inequalities are proved connecting the eigenvalue spread of a Hermitian matix to the eigenvalue spreads of its collection of principal submatrices. An application is made to the numerical range of general matrices.     

On the eigenvalues of principal submatrices of J-normal matrices

The problem of the existence of a J-normal matrix A when its spectrum and the spectrum of some of its (n-1)×(n-1) principal submatrices are prescribed is analyzed. The case of 3×3 matrices is particularly investigated. The results here obtained in the framework of indefinite inner product spaces are in the spirit of those due to Nylen, Tam and Uhlig.     

The eigenvalue spreads of a hermitian matrix and its principal submatrices

Inequalities are proved connecting the eigenvalue spread of a Hermitian matix to the eigenvalue spreads of its collection of principal submatrices. An application is made to the numerical range of general matrices.     

On the product of the diagonal elements of hermitian matrices

In [5] M. Marcus stated a conjecture concerning the product of the diagonal elements of normal matrices which is false [6]. In this paper we prove that such a conjecture is true in the Hermitian case.     

Permuting matrices to avoid forbidden submatrices

This paper attaches a frame to a natural class of combinatorial problems and points out that this class includes many important special cases.

A matrix M is said to avoid a set of matrices if M does not contain any element of as (ordered) submatrix. For a fixed set of matrices, we consider the problem of deciding whether the rows and columns of a matrix can be permuted in such a way that the resulting matrix M avoids all matrices in .

We survey several known and new results on the algorithmic complexity of this problem, mostly dealing with (0,1)-matrices. Among others, we will prove that the problem is polynomial time solvable for many sets containing a single, small matrix and we will exhibit some example sets for which the problem is NP-complete.     

Irreducible matrices with reducible principal submatrices

Let A be a (0, 1)-matrix of order n 3 and let s_i⁰(A), i = 1, …, n, be the number of the off diagonal 0's in row and column i of A. We prove that if A is irreducible, and if all its principal submatrices of order (n − 1) are reducible, then s_i⁰(A) n − 1; i = 1, …, n. This establishes the validity of a conjecture by B. Schwarz concerning strongly connected graphs and their primal subgraphs.     

Properties of submatrices of Sylvester Hadamard matrices

We investigate the algebraic behaviour of leading principal submatrices of Hadamard matrices being powers of 2. We provide analytically the spectrum of general submatrices of these Hadamard matrices. Symmetry properties and relationships between the upper left and lower right corners of the matrices in this respect are demonstrated. Considering the specific construction scheme of this particular class of Hadamard matrices (called Sylvester Hadamard matrices), we utilize tensor operations to prove the respective results. An algorithmic procedure yielding the complete spectrum of leading principal submatrices of Sylvester Hadamard matrices is proposed.     

Spectra of principal submatrices of nonnegative matrices

Let A be an n×n nonnegative matrix with the spectrum (λ₁,λ₂,…,λ_n) and let A₁ be an m×m principal submatrix of A with the spectrum (μ₁,μ₂,…,μ_m). In this paper we present some cases where the realizability of (μ₁,μ₂,…,μ_m,ν₁,ν₂,…,ν_s) implies the realizability of (λ₁,λ₂,…,λ_n,ν₁,ν₂,…,ν_s) and consider the question whether this holds in general. In particular, we show that the list

(λ₁,λ₂,…,λ_n,-μ₁,-μ₂,…,-μ_m)