On principal submatrices

It is shown that if A[ω] is a principal submatrix of the positive definite Hermitian matrix A, then A ^-1[ω] -(A[ω])^-1is a positive semidefinite hermitian matrix. This fact is used to give a brief proof of a result of Saburou Saitoh concerning Hadamard products.     

On principal submatrices

It is shown that if A[ω] is a principal submatrix of the positive definite Hermitian matrix A, then A ^?1[ω] ?(A[ω])^?1is a positive semidefinite hermitian matrix. This fact is used to give a brief proof of a result of Saburou Saitoh concerning Hadamard products.     

Operator norms of submatrices

Translated from Matematicheskie Zametki, Vol. 45, No. 3, pp. 94–100, March, 1989.     

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.     

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.     

Eigenvalue inequalities for principal submatrices

For a polynomial with real roots, inequalities between those roots and the roots of the derivative are demonstrated and translated into eigenvalue inequalities for a hermitian matrix and its submatrices. For example, given an n-by-n positive definite hermitian matrix with maximum eigenvalue λ, these inequalities imply that some principal submatrix has an eigenvalue exceeding $\text{[(}\text{n?1)}\text{n}\text{]λ}$.     

Eigenvalues of completions of submatrices

This paper concerns the following problem:Given a submatrix of an n× nmatrix Ztogether with its position in Z, determine the restrictions imposed on the eigenvalues of Zand their elementary divisors by this prescribed part. The terms on which the final results depend are identified as the block similarity invariants. Special cases, which were considered before, are reviewed, and the case of off-diagonal blocks is solved.     

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.     

Numerical ranges of principal submatrices

It is shown that the ratio of the area of the convex hull of the fields of values of the (n?1)-by-(n?1) principal submatrices of an n-by-n matrix A to the area of the field of values of A is bounded below by a function of n which approaches 1 as n approaches ∞. Since this convex hull is necessarily contained in the field of values of A, an interpretation is that, asymptotically in the dimension, the field of any given matrix is “filled up” by the fields of the submatrices (collectively). Some new inequalities for the eigenvalues of principal submatrices of hermitian matrices, which are not implied by interlacing, are employed.     

On operator norms of submatrices

Both of the following conditions are equivalent to the absoluteness of a norm ν in $\text{C}$ⁿ: (1) for all n×n diagonal matrices D=(d_k), the subordinate operator norm N_ν(D)=max_k|d_k|; (2) for all n×n matrices A, N_ν(A) ?N_ν(|A|). These conditions are modified for partitioned matrices by replacing absolute values with norms of blocks. A generalization of absoluteness is thus obtained.     

Off-diagonal submatrices of a Hermitian matrix

A necessary and sufficient condition is given to a complex matrix to be an off-diagonal block of an Hermitian matrix with prescribed eigenvalues (in terms of the eigenvalues of and singular values of ). The proof depends on some recent breakthroughs in the study of spectral inequalities on the sum of Hermitian matrices by Klyachko and Fulton. Some interesting geometrical properties of the set of all such matrices are derived from the main result. These results improve earlier ones that only give partial information for the set .

     

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.     

Almost orthogonal submatrices of an orthogonal matrix

Lett≥1 and letn, M be natural numbers,n<M. Leta=(a _i,j ) be ann xM matrix whose rows are orthonormal. Suppose that the ℓ₂-norms of the columns ofA are uniformly bounded. Namely, for allj Using majorizing measure estimates we prove that for every ε>0 there exists, a setI ⊃ {1,…,M} of cardinality at most such that the matrix , whereA _I =(a _i,j ) _j∈I , acts as a (1+ε)-isomorphism from ℓ ₂ ⁿ into . Research supported in part by a grant of the US-Israel BSF. Part of this research was performed when the author held a postdoctoral position at MSRI. Research at MSRI was supported in part by NSF grant DMS-9022140.     

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.     

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.     

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.