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.     

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.     

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.     

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.     

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)     

New weighing matrices constructed from two circulant submatrices

A number of new weighing matrices constructed from two circulants and via a direct sum construction are presented, thus resolving several open cases for weighing matrices as these are listed in the second edition of the Handbook of Combinatorial Designs.     

On determinants of nonprincipal submatrices of hermitian matrices

It is our purpose to compute the maximum value of the modulus of the determinant of an m×m nonprincipal submatrix of an n×n hermitian (or real symmetric) matrix A, in terms of m, the eigenvalues of A, and the cardinality k of the set of common row and column indices of this submatrix.     

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 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.     

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.     

A note on convexity and submatrices of distance matrices

We prove that, if the index set of a distance matrix cannot be partitioned into two convex subsets, then, given a pair of indices, we can find another pair such that the principal submatrix of order four associated with the four indices is nontree-realizable.     

Extremal functions of forbidden multidimensional matrices

Pattern avoidance is a central topic in graph theory and combinatorics. Pattern avoidance in matrices has applications in computer science and engineering, such as robot motion planning and VLSI circuit design. A $d$-dimensional zero–one matrix $A$ avoids another$d$-dimensional zero–one matrix $P$ if no submatrix of $A$ can be transformed to $P$ by changing some ones to zeros. A fundamental problem is to study the maximum number of nonzero entries in a $d$-dimensional $n\times ?\times n$ matrix that avoids $P$. This maximum number, denoted by $f(n,P,d)$, is called the extremal function.We advance the extremal theory of matrices in two directions. The methods that we use come from combinatorics, probability, and analysis. Firstly, we obtain non-trivial lower and upper bounds on $f(n,P,d)$ when $n$ is large for every $d$-dimensional block permutation matrix $P$. We establish the tight bound $\Theta \left(n^{d?1}\right)$ on $f(n,P,d)$ for every $d$-dimensional tuple permutation matrix $P$. This tight bound has the lowest possible order that an extremal function of a nontrivial matrix can ever achieve. Secondly, we show that the limit inferior of the sequence $\left\{\frac{f(n,P,d)}{n^{d?1}}\right\}$ has a lower bound $2^{\Omega \left(k^{1∕2}\right)}$ for a family of $k\times ?\times k$ permutation matrices $P$. We also improve the upper bound on the limit superior from $2^{O(klogk)}$ to $2^{O\left(k\right)}$ for all $k\times ?\times k$ permutation matrices and show that the new upper bound also holds for tuple permutation matrices.     

Extremal functions of forbidden double permutation matrices

We say a 0–1 matrix A avoids a matrix P if no submatrix of A can be transformed into P by changing some ones to zeroes. We call P an m-tuple permutation matrix if P can be obtained by replacing each column of a permutation matrix with m copies of that column. In this paper, we investigate n×n matrices that avoid P and the maximum number ex(n,P) of ones that they can have. We prove a linear bound on ex(n,P) for any 2-tuple permutation matrix P, resolving a conjecture of Keszegh [B. Keszegh, On linear forbidden matrices, J. Combin. Theory Ser. A 116 (1) (2009) 232–241]. Using this result, we obtain a linear bound on ex(n,P) for any m-tuple permutation matrix P. Additionally, we demonstrate the existence of infinitely many minimal non-linear patterns, resolving another conjecture of Keszegh from the same paper.     

Approximation of eigenvalues for unbounded Jacobi matrices using finite submatrices

We consider an infinite Jacobi matrix with off-diagonal entries dominated by the diagonal entries going to infinity. The corresponding self-adjoint operator J has discrete spectrum and our purpose is to present results on the approximation of eigenvalues of J by eigenvalues of its finite submatrices.     

A forbidden structure of ray nonsingular matrices

A complex square matrix is called a ray nonsingular matrix (RNS matrix) if its ray pattern implies that it is nonsingular. In this paper, a necessary condition for RNS matrices is provided by showing that if A=I−A(D)$A=I-A(D)$ is ray nonsingular, then the arc weighted digraph D contains no forbidden cycle chains.     

Enumeration of matrices of given rank with submatrices of given rank

The authors determine the number of (n+m)×t matrices A¹ of rank r+v, over a finite field GF(q), whose last m rows are those of a given matrix A of rank r+v over GF(q) and whose first n rows have a given rank u.