The extent to which triangular sub-patterns explain minimum rank

For any zero-nonzero pattern of a matrix, the minimum possible rank is at least the size of a sub-pattern that is permutation equivalent to a triangular pattern with nonzero diagonal. For certain numbers of rows and columns, the minimum rank of a pattern is k only when there is a k-by-k such triangle. Here, we complete the determination of such sizes by showing that an m-by-n pattern of minimum rank k must contain a k-triangle for m=5, k=4; m=6, k=5; and m=6, k=4. A table is given showing whether or not this happens for all m, n, k. In the process, a Schur complement approach to minimum rank is described and used, and simple ways to recognize the presence of triangles of sizes less than 7 are given.     

A new result on the problem of Zarankiewicz

Zarankiewicz (Colloq. Math.2 (1951), 301) raised the following problem: Determine the least positive integer z(m, n, j, k) such that each 0–1-matrix with m rows and n columns containing z(m, n, j, k) ones has a submatrix with j rows and k columns consisting entirely of ones. This paper improves a result of Hylten-Cavallius (Colloq. Math.6 (1958), 59–65) who proved: $\text{[}\text{k}\text{2}\text{]}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{?}\text{lim}{}_{\mathrm{n\to \infty }}\text{inf}\text{z(n, n, 2, k)n}{}^{\mathrm{<mtext>?</mtext><mtext>3</mtext><mtext>2</mtext>}}\text{?}\text{lim}{}_{\mathrm{n\to \infty }}\text{sup}\text{z(n, n, 2, k)n}{}^{\mathrm{<mtext>?</mtext><mtext>3</mtext><mtext>2</mtext>}}\text{? (k ? 1)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. We prove that $\text{lim}{}_{\mathrm{n\to \infty }}\text{z(n, n, 2, k)n}{}^{\mathrm{<mtext>?</mtext><mtext>3</mtext><mtext>2</mtext>}}$ exists and is equal to $\text{(k ? 1)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. For the special case where k = 2 resp. k = 3 this result was proved earlier by Kövari, Sos and Turan (Colloq. Math.3 (1954), 50–57) resp. Hylten-Cavallius.     

Accurate approximation of time-varying matrices of linear differential systems

We consider the problem of the identification of the time-varying matrix A(t) of a linear m-dimensional differential system y′ = A(t)y. We develop an approximation A_n,k = ∑ⁿ_{j ? 1}c_j{Y(t_k + τ_j) Y^?1(t_k) ? I} to A(t_k) for grid points t_k = a + kh, k = 0,…, N using specified τ_j = θ_jh, 0 < θ_j < 1, j = 1, …, n, and show that for each t_k, the L₁ norm of the error matrix is $\text{O}$(hⁿ). We demonstrate an efficient scheme for the evaluation of A_n,k and treat sample problems.     

A subdeterminant inequality for normal matrices

Let A be an n × n normal matrix over $\text{C}$, and Q_m, _n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Q_m, _n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i₁,…, i_k, i_k+1,…, i_m, such that α(i_j) = β(i_j), i = 1,…, k, and {α(i_k+1),…, α(i_m) } ∩ {β(i_k+1),…, β(i_m) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let $\text{U}$_n be the group of n × n unitary matrices. Define the nonnegative number

where | α ∩ β| = k. It is proved that

Let A be semidefinite hermitian. We conjecture that ρ₀(A) ? ρ₁(A) ? ··· ? ρ_m(A). These inequalities have been tested by machine calculations.     

A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks

A fast solution algorithm is proposed for solving block banded block Toeplitz systems with non-banded Toeplitz blocks. The algorithm constructs the circulant transformation of a given Toeplitz system and then by means of the Sherman-Morrison-Woodbury formula transforms its inverse to an inverse of the original matrix. The block circulant matrix with Toeplitz blocks is converted to a block diagonal matrix with Toeplitz blocks, and the resulting Toeplitz systems are solved by means of a fast Toeplitz solver.The computational complexity in the case one uses fast Toeplitz solvers is equal to ξ(m,n,k)=O(mn³)+O(k³n³) flops, there are m block rows and m block columns in the matrix, n is the order of blocks, 2k+1 is the bandwidth. The validity of the approach is illustrated by numerical experiments.     

The maximum distance problem and band sequences

We solve the following problem. For 1 ⩽ j, k ⩽ n and |j − k| ⩽ m, let a_jk be a given complex number with a_kj = ā_jk. We wish to find linearly independent vectors x₁,…,x_n such that 〈x_k, x_j〉 = a_jk for |j − k| ⩽ m and such that the distance from x_k to the linear span of x₁,…,x_k−1 is maximal for 2 ⩽ k ⩽ n. We construct and characterize all such sequences of vectors. Our solution leads naturally to the class of m-band sequences of vectors in an inner product space. We study these sequences and characterize their equivalence classes under unitary transformations.     

On orthogonal matrices with constant diagonal

In connection with the problem of finding the best projections of k-dimensional spaces embedded in n-dimensional spaces Hermann König asked: Given m∈$\text{R}$ and n∈$\text{N}$, are there n×n matrices C=(c_ij), i, j=1,…,n, such that c_ii=m for all i, |c_ij|=1 for i≠j, and C²=(m²+n?1)I_n? König was especially interested in symmetric C, and we find some families of matrices satisfying this condition. We also find some families of matrices satisfying the less restrictive condition CC^T=(m²+n?1)I_n.     

A Fisher type inequality

In this paper we study subsets of a finite set that intersect each other in at most one element. Each subset intersects most of the other subsets in exactly one element. The following theorem is one of our main conclusions. Let S₁,… S_m be m subsets of an n-set S with |S₁| ? 2 (l = 1, …,m) and |S_i ∩ S_j| ? 1 (i ≠ j; i, j = 1, …, m). Suppose further that for some fixed positive integer c each S_i has non-empty intersection with at least m ? c of the remaining subsets. Then there is a least positive integer M(c) depending only on c such that either m ? n or m ? M(c).     

Decomposable bilinear numerical radii

Let A be an n-square normal matrix over $\text{C}$, and Q_{m, n} be the set of strictly increasing integer sequences of length m chosen from 1,…, n. For α,β∈Q_{m, n} denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k∈{0,1,…,m} write z.sfnc;α∩β|=k if there exists a rearrangement of 1,…,m, say i₁,…,i_k, i_k+1,…,i_m, such that α(i_j)=β(i_j), j=1,…,k, and {α(i_k+1),…,α(i_m)};∩{β(i_k+1),…,β(i_m)}=ø. Let

be the group of n-square unitary matrices. Define the nonnegative number

$\text{?}{}_{\mathrm{k}}\text{(A)=}\text{max}\text{U∈}\textcolor{red}{}\text{|}\text{det}\text{(U}{}^1\text{AU) [α|β]|}$

, where |α∩β|=k. Theorem 1 establishes a bound for ?_k(A), 0?k<m?1, in terms of a classical variational inequality due to Fermat. Let A be positive semidefinite Hermitian, n?2m. Theorem 2 leads to an interlacing inequality which, in the case n=4, m=2, resolves in the affirmative the conjecture that

$\text{?}{}_{\mathrm{m}}\text{(A)??}{}_{\mathrm{m?1}}\text{(A)????}{}_0\text{(A)}$

.     

The extension of the D(?k 2)-pair {k 2,k 2 + 1}

Let n be a nonzero integer. A set of m distinct positive integers is called a D(n)-m-tuple if the product of any two of them increased by n is a perfect square. Let k be a positive integer. In this paper, we show that if {k ², k ²+1, c, d} is a D(?k ²)-quadruple with c < d, then c = 1 and d = 4k ²+1. This extends the work of the first author [20] and that of Dujella [4].     

The Asymptotic Behavior of a Family of Sequences via Tauberian Theorems

We study the asymptotic behavior of a family of sequences defined by the following nonlinear induction relation c₀ = 1 and c_n ∑^k_{j = 1} r_jc_[n/mj] + ∑^k_{j = k + 1} r_jc_{[(n + 1)^1/mj] − 1} for n ≥ 1, where the r_j are real positive numbers and m_j are integers greater than or equal to 2. Depending on the fact that ∑^k_{j = 1} r_j is greater or lower than 1, we prove that c_n/n^α or c_n/(ln n)^α goes to some finite limit for some explicit α. Our study is based on Tauberian theorems and extends a result of Erdös et al.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

Sequences of orthogonal vectors with a fixed norm

Let A = (a_ij) be an n × m matrix with a_ij ∈ K, a field of characteristic not 2, where Σ_i=1ⁿa_ij² = e, 1 ≤ j ≤ m, and Σ_i=1ⁿa_ija_ij′ = 0 for j ≠ j′. The question then is when is it possible to extend A, by adding columns, to obtain a matrix with orthogonal columns of the same norm. The question is answered for n ? 7 ≤ m ≤ n as well as for more general cases. Complete solutions are given for global and local fields, the answer depending on what congruence class modulo 4 n belongs to and how few squares are needed to sum to e.     

Integers divisible by sums of powers of their prime factors

For each positive integer j, let βj(n):=_∑p|npj. Given a fixed positive integer k, we show that there are infinitely many positive integers n having at least two distinct prime factors and such that βj(n)|n for each j∈{1,2,…,k}.     

Refined enumerations of alternating sign matrices: monotone (<Emphasis Type="Italic">d</Emphasis>,<Emphasis Type="Italic">m</Emphasis>)-trapezoids with prescribed top and bottom row

Monotone triangles are plane integer arrays of triangular shape with certain monotonicity conditions along rows and diagonals. Their significance is mainly due to the fact that they correspond to n×n alternating sign matrices when prescribing (1,2,…,n) as bottom row of the array. We define monotone (d,m)-trapezoids as monotone triangles with m rows where the d−1 top rows are removed. (These objects are also equivalent to certain partial alternating sign matrices.) It is known that the number of monotone triangles with bottom row (k ₁,…,k _n ) is given by a polynomial α(n;k ₁,…,k _n ) in the k _i ’s. The main purpose of this paper is to show that the number of monotone (d,m)-trapezoids with prescribed top and bottom row appears as a coefficient in the expansion of a specialisation of α(n;k ₁,…,k _n ) with respect to a certain polynomial basis. This settles a generalisation of a recent conjecture of Romik et al. (Adv. Math. 222:2004–2035, 2009). Among other things, the result is used to express the number of monotone triangles with bottom row (1,2,…,i−1,i+1,…,j−1,j+1,…,n) (which is, by the standard bijection, also the number of n×n alternating sign matrices with given top two rows) in terms of the number of n×n alternating sign matrices with prescribed top and bottom row, and, by a formula of Stroganov for the latter numbers, to provide an explicit formula for the first numbers. (A formula of this type was first derived by Karklinsky and Romik using the relation of alternating sign matrices to the six-vertex model.)     

Natural frequencies of a multi-degree-of-freedom vibration system

A chain structured mass-spring vibration system with N degrees of freedom is considered where massesM _j = m_jm = m/j and spring stiffnesses k_j = c_jk = (N + 1 - j)k, j = 1, …, N, have been applied. The conjecture of Mikota [1] on the natural frequencies is discussed showing how difficult it is to find an explicit solution of the related eigenvalue problem. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Doubly stochastic matrices with equal subpermanents

It has been conjectured that if A is a doubly stochastic n>× n matrix such that per A(i, j)≥perA for all i, j, then either A = J_n, then n × n matrix with each entry equal to $\text{1}\text{n}$, or, up to permutations of rows and columns, $\text{A =}\text{1}\text{2}\text{(I}{}_{\mathrm{n}}\text{+ P}{}_{\mathrm{n}}\text{)}$, where P_n is a full cycle permutation matrix. This conjecture is proved.     

Random systems of equations in free abelian groups

We study the solvability of random systems of equations on the free abelian group ? ^m of rank m. Denote by SAT(? ^m , k, n) and \(SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)\) the sets of all systems of n equations of k unknowns in ? ^m satisfiable in ? ^m and ? ^m respectively. We prove that the asymptotic density \(\rho \left( {SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)} \right)\) of the set \(SAT_{\mathbb{Q}^m } (\mathbb{Z}^m ,k,n)\) equals 1 for n ≤ k and 0 for n > k. As regards, SAT(? ^m , k, n) for n < k, some new estimates are obtained for the lower and upper asymptotic densities and it is proved that they lie between (Π _j=k?n+1 ^k ζ(j))^?1 and \(\left( {\tfrac{{\zeta (k + m)}} {{\zeta (k)}}} \right)^n\) , where ξ(s) is the Riemann zeta function. For n ≤ k, a connection is established between the asymptotic density of SAT(? ^m , k, n) and the sums of inverse greater divisors over matrices of full rank. Starting from this result, we make a conjecture about the asymptotic density of SAT(? ^m , n, n). We prove that ρ(SAT(? ^m , k, n)) = 0 for n > k.     

Centers for a 6-parameter family of polynomial vector fields of arbitrary degree

For all non-negative integers n₁,n₂,n₃,j₁,j₂ and j₃ with nk+jk>1 for k=1,2,3, (nk,jk)≠(nl,jl) if k≠l, j₃=n₃−1 and jk≠nk−1 for k=1,2, we study the center variety of the 6-parameter family of real planar polynomial vector given, in complex notation, by , where z=x+iy and A,B,C∈C\{0}.     

Forbidden submatrices

We consider a m × n (0, 1)-matrix A, no repeated columns, which has no k × l sumatrix F. We may deduce bounds on n, polynomial in m, depending on F. The best general bound is O(m^2k−1). We improve this and provide best possible bounds for k × 1 F's and certain k × 2 F's. In the case that all columns of F are the same, good bounds are obtained which are best possible for l = 2 and some other cases. Good bounds for 1 × l F's are provided, namely n ⩽ (l−1)m + 1, which are shown to be best possible for F = [1010...10]. The paper finishes with a study of the 14 different 3 × 2 possibilities for F, solving all but 3.