Linear mappings which are rank-k nonincreasing, II

We prove the following result. Let F be an infinite field of characteristic other than two. Let k be a positive integer. Let S_n(F) denote the space of all n × n symmetric matrices with entries in F, and let T:S_n(F)→S_n(F) be a linear operator. Suppose that T is rank-k nonincreasing and its image contains a matrix with rank higher than K. Then, there exist λεF and PεF^n,n such that T(A)=λPAP^t for all AεS_n(F). λ can be chosen to be 1 if F is algebraically closed and ±1 if F=R, the real field.     

On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

The cycle structure of regular multipartite tournaments

A multipartite tournament is an orientation of a complete multipartite graph. A tournament is a multipartite tournament, each partite set of which contains exactly one vertex. Alspach (Canad. Math. Bull. 10 (1967) 283) proved that every regular tournament is arc-pancyclic. Although all partite sets of a regular multipartite tournament have the same cardinality, Alspach's theorem is not valid for regular multipartite tournaments. In this paper, we prove that if the cardinality common to all partite sets of a regular n-partite (n3) tournament T is odd, then every arc of T is in a cycle that contains vertices from exactly m partite sets for all m{3,4,…,n}. This result extends Alspach's theorem for regular tournaments to regular multipartite tournaments. We also examine the structure of cycles through arcs in regular multipartite tournaments.     

Some Ore-type Results for Matching and Perfect Matching in <Emphasis Type="Italic">k</Emphasis>-uniform Hypergraphs

Let S₁ and S₂ be two (k-1)-subsets in a k-uniform hypergraph H. We call S₁ and S₂ strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S₁ ∩ e ≠∅ and S₂ ∩ e ≠∅ or e ⊆ S₁ ∪ S₂ or e ⊇ S₁ ∪ S₂, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k²-k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k-1)-sets equal to 2n-4(k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k-2)k. If the degree sum of any two middle independent (k-1)-subsets is larger than 2(d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.     

Embedding complete trees into the hypercube

We consider embeddings of the complete t-ary trees of depth k (denotation T^k,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(T^k,t), is known if max{k,t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(T^k,3)2k+1 up to lim_k→∞dim(T^k,3)/k5/3 and show lim_t→∞dim(T^3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(T^k,t) for arbitrary k and t.     

Linear operators preserving the higher numerical radius of matrices

A linear operator T on a matrix space is said to be unital if T(I) = I. In this note we characterize the unital lineart operators on matrix spaces that preserve the k-numerical radius. Using the results obtained we easily determine the structure of all linear operators on the space of n × n complex matrices that preserve the k-numerical range. This completes the work of Pierce and Watking, who obtained the results for the cases when n ≠ n2k.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

The Best Lower Bound for the Permanent of a Correlation Matrix of Rank Two

If 1≤k≤n, then Cor(n,k) denotes the set of all n×n real correlation matrices of rank not exceeding k. Grone and Pierce have shown that if A∈Cor (n, n-1), then per(A)≥n/(n-1). We show that if A∈Cor(n,2), then , and that this inequality is the best possible.     

Equality of higher numerical ranges of matrices and a conjecture of Kippenhahn on Hermitian pencils

Let M_n be the algebra of all n × n complex matrices. For 1 k n, the kth numerical range of A M_n is defined by W_k(A) = (1/k)∑_j^k=1x_j^*Ax_j : x₁, …, x_k is an orthonormal set in ⁿ]. It is known that tr A/n = W_n(A) W_n−1(A) W₁(A). We study the condition on A under which W_m(A) = W_k(A) for some given 1 m < k n. It turns out that this study is closely related to a conjecture of Kippenhahn on Hermitian pencils. A new class of counterexamples to the conjecture is constructed, based on the theory of the numerical range.     

Large spaces of symmetric matrices of bounded rank are decomposable

Let k and n be positive integers such that k≤n. Let S_n(F) denote the space of all n×n symmetric matrices over the field F with char F≠2. A subspace L of S_n(F) is said to be a k-subspace if rank A≤k for every AεL.

Now suppose that k is even, and write k=2r. We say a k∥-subspace of S_n(F) is decomposable if there exists in Fⁿ a subspace W of dimension n-r such that x^tAx=0 for every xεWAεL.

We show here, under some mild assumptions on kn and F, that every k∥-subspace of S_n(F) of sufficiently large dimension must be decomposable. This is an analogue of a result obtained by Atkinson and Lloyd for corresponding subspaces of F^m,n.     

Embeddings of the base and bundle isomorphisms

Let π_i :E_i→M, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections s_i :M→E_i. Suppose that U is an open neighborhood of s₁(M) in E₁ and F :U→E₂ a smooth embedding so that π₂Fs₁ :M→M is homotopic to a diffeomorphism f. We show that if k>[(n+1)/2]+1 then E₁ and the induced bundle f^*E₂ are isomorphic as oriented bundles provided that f have degree +1; the same conclusion holds if f has degree −1 except in the case where k is even and one of the bundles does not have a nowhere-zero cross-section. For n≡0(4) and [(n+1)/2]+1<kn we give examples of nonisomorphic oriented bundles E₁ and E₂ of rank k over a homotopy n-sphere with total spaces diffeomorphic with orientation preserved, but such that E₁ and f^*E₂ are not isomorphic oriented bundles. We obtain similar results and counterexamples in the more difficult limiting case where k=[(n+1)/2]+1 and M is a homotopy n-sphere.     

The existence of Schröder designs with equal-sized holes

A holey Schröder design of type h₁^n₁h₂^n₂ … h_k^n_k (HSD(h₁^n₁h₂^n₂ … h_k^n_k)) is equivalent to a frame idempotent Schröder quasigroup (FISQ(h₁^n₁h₂^n₂ … h_k^n_k)) of order n with n_i missing subquasigroups (holes) of order h_i, (1 i k), which are disjoint and spanning, that is, Σ_{1 i k} n_ih_i = n. In this paper, it is shown that an HSD(hⁿ) exists if and only if h²n(n − 1) 0 (mod 4) with expceptions (h, n) ε {{(1,5),(1,9),(2,4)}} and the possible exception of (h, n) = (6,4).     

Path polynomials of a circuit: a constructive approach

Let P_k denote the polynomial of the path on k vertices. We describe completely the matrix P_k (C_n), where C_n is the circuit on n vertices, using some important concepts of theory of circulant matrices. We also consider Q _k, the polynomial of the circuit on kvertices.

Using orthogonal polynomials we present constructive proofs of some results obtained recently by Bapat and Lai, Beezer and Ronghua.     

A result about determinantal divisors

Let Rbe a principal ideal ringR_n the ring of n× nmatrices over R, and d_k(A) the kth determinantal divisor of Afor 1 ≤ k≤ n, where Ais any element of R_n, It is shown that if A,BεR_n, det(A) det(B:) ≠ 0, then d_k(AB) ≡ 0 mod d_k(A) d_k(B). If in addition (det(A), det(B)) = 1, then it is also shown that d_k(AB) = d_k(A) d_k(B). This provides a new proof of the multiplicativity of the Smith normal form for matrices with relatively prime determinants.     

Subpermanents of doubly stochastic matrices

It is shown that if all subpermaneats of order k of an n × n doubly stochastic matrix are equal for some k ≤ n - 2, then all the entries of the matrix must be equal to 1/n.     

A reversal index for tournament matrices *

Given a tournament matrix T, its reversal indexi_R (T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R (T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R (T)≤[(n?1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n?1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

Matrices that preserve vectors of fixed sign variation

For each k≥ 0, those nonsingular matrices that transform the set of totally nonzero vectors with k sign variations into (respectively, onto) itself are studied. Necessary and sufficient conditions are provided. The cases k=0,1,2,n-3,n-2,n-1 are completely characterized.     

Compound connection matrices

Suppose T is an incidence, basis circuit or basis cut set matrix of a connected graph and T^(k) is the k compound of T. It is proven that any second order minor of T^(k) is equal +1, −1, or 0. For the case of an incidence matrix this result is applied to tree counting and some structural properties of T^(k) are given.     

Non-naturally reductive Einstein metrics on Sp(n)

We prove that Sp(2k+l)admits at least two non-naturally reductive Einstein metrics which are Ad(Sp(k)×Sp(k)×Sp(l))-invariant ifk<1.It implies that every compact simple Lie group Sp(n)for n≥4 admits at least 2[(n-1)/3]non-naturally reductive left-invariant Einstein metrics.     

On the sum powers of matrices

A theorem of Lagrange says that every natural number is the sum of 4 squares. M. Newman proved that every integral n by n matrix is the sum of 8 (-1)ⁿ squares when n is at least 2. He asked to generalize this to the rings of integers of algebraic number fields. We show that an n by n matrix over a a commutative R with 1 is the sum of squares if and only if its trace reduced modulo 2Ris a square in the ring R/2R. It this is the case (and n is at least 2), then the matrix is the sum of 6 squares (5 squares would do when n is even). Moreover, we obtain a similar result for an arbitrary ring R with 1. Answering another question of M. Newman, we show that every integral n by n matrix is the sum of ten k-th powers for all sufficiently large n. (depending on k).