Simple product colorings

If A is a set colored with m colors, and B is colored with n colors, the coloring of A × B obtained by coloring (a, b) with the pair (color of a, color of b) will be called an m × n simple product coloring (SPC) of A × B. SPC's of Cartesian products of three or more sets are defined analogously. It is shown that there are 2 × 2, and 2 × 2 × 2 SPC's of $\text{Q}$² and $\text{Q}$³ which forbid the distance one; that there is no 2^k SPC of $\text{Q}$^k forbidding the distance one, for k > 3; and that there is no 2 × 2 SPC of $\text{Q}$ × $\text{Q}$(√15), and thus none of $\text{R}$², forbidding the distance 1.     

On the parity of the frequency of cycle lengths of shift register sequences

Let A(n, k) be the number of k-long cycles generated by binary shift registers of span n ? 2. It is shown that A(n, k) is odd if and only if $\text{k =}\text{1}\text{3}\text{[2}{}^{\mathrm{n+1}}\text{± 3 + (?1)}{}^{\mathrm{n}}\text{]}$. A recursive construction of complete self-dual, self-reversing cycles of these lengths is presented.     

Spaces of matrices of equal rank

Let M_m,n(F) denote the space of all mXn matrices over the algebraically closed field F. A subspace of M_m,n(F), all of whose nonzero elements have rank k, is said to be essentially decomposable if there exist nonsingular mXn matrices U and V respectively such that for any element A, UAV has the form

$\text{UAV=}\text{A}{}_1\text{A}{}_2\text{A}{}_3\text{0}$

where A₁ is iX(k–i) for some i?k. Theorem: If $\text{K}$ is a space of rank k matrices, then either $\text{K}$ is essentially decomposable or dim $\text{K}$?k+1. An example shows that the above bound on non-essentially-decomposable spaces of rank k matrices is sharp whenever n?2k–1.     

Geometric conditions for the existence of positive eigenvalues of matrices

Finite-dimensional theorems of Perron-Frobenius type are proved. For A∈$\text{C}$ⁿⁿ and a nonnegative integer k, we let w_k (A) be the cone generated by A^k, A^k+1,…in $\text{C}$ⁿⁿ. We show that A satisfies the Perron-Schaefer condition if and only if the closure $\text{W}$_k(A) of w_k(A) is a pointed cone. This theorem is closely related to several known results. If k?v₀(A), the index of the eigenvalue 0 in spec A, we prove that A has a positive eigenvalue if and only if w_k(A) is a pointed nonzero cone or, equivalently $\text{W}$_k(A) is not a real subspace of $\text{C}$ⁿⁿ. Our proofs are elementary and based on a method of Birkhoff's. We discuss the relation of this method to Pringsheim's theorem.     

Sperner families over a subset

Let |X| = n > 0, |Y| = k > 0, and Y ? X. A family A of subsets of X is a Sperner family of X over Y if A₁A₂ for every pair of distinct members of A and every member of A has a nonempty intersection with Y. The maximum cardinality f(n, k) of such a family is determined in this paper. $\text{f(n,k)=(}\text{n}\text{[n}\text{2]}\text{)?(}\text{?k}\text{[n}\text{2]}\text{)}$.     

Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function

The permanent function is used to determine geometrical properties of the set $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then $\text{F}$ corresponds to an n × n (0, 1)-matrix A, where the permanent of A is the number of vertices of $\text{F}$. If A is fully indecomposable, then the dimension of $\text{F}$ equals σ(A) ? 2n + 1, where σ(A) is the number of 1's in A. The only two-dimensional faces of $\text{Ω}{}_{\mathrm{n}}$ are triangles and rectangles. For n ? 6, $\text{Ω}{}_{\mathrm{n}}$ has four types of three-dimensional faces. The facets of the faces of $\text{Ω}{}_{\mathrm{n}}$ are characterized. Faces of $\text{Ω}{}_{\mathrm{n}}$ which are simplices are determined. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is two-neighborly but not a simplex, then $\text{F}$ has dimension 4 and six vertices. All k-dimensional faces with k + 2 vertices are determined. The maximum number of vertices of a k-dimensional face is 2^k. All k-dimensional faces with at least 2^k?1 + 1 vertices are determined.     

Duality in hypercomplex function theory

Let $\text{A}$ be the Clifford algebra constructed over a quadratic n-dimensional real vector space with orthogonal basis {e₁,…, e_n}, and e₀ be the identity of $\text{A}$. Furthermore, let M_k(Ω;$\text{A}$) be the set of $\text{A}$-valued functions defined in an open subset Ω of R^m+1 (1 ? m ? n) which satisfy D^kf = 0 in Ω, where D is the generalized Cauchy-Riemann operator $\text{D = ∑}{}_{\mathrm{i\; =\; 0}}{}^{\mathrm{m}}\text{e}{}_{\mathrm{i}}\text{(}\text{?}\text{?x}{}_{\mathrm{i}}\text{)}$ and k? N. The aim of this paper is to characterize the dual and bidual of M_k(Ω;$\text{A}$). It is proved that, if M_k(Ω;$\text{A}$) is provided with the topology of uniform compact convergence, then its strong dual is topologically isomorphic to an inductive limit space of Fréchet modules, which in its turn admits M_k(Ω;$\text{A}$) as its dual. In this way, classical results about the spaces of holomorphic functions and analytic functionals are generalized.     

Semisimilarity for matrices over a division ring

Two square matrices A and B over a ring R are semisimilar, written A$\text{?}$B, if YAX=B and XBY=A for some (possibly rectangular) matrices X, Y over R. We show that if A and B have the same dimension, and if the ring is a division ring $\text{D}$, then A$\text{?}$B if and only if A² is similar to B² and rank(A^k)=rank(B^k), k=1,2,…     

Nonnegative factorization of completely positive matrices

Let A be a real symmetric n × n matrix of rank k, and suppose that A = BB′ for some real n × m matrix B with nonnegative entries (for some m). (Such an A is called completely positive.) It is shown that such a B exists with $\text{m?}\text{1}\text{2}\text{k(k+1)?N}$, where 2N is the maximal number of (off-diagonal) entries which equal zero in a nonsingular principal submatrix of A. An example is given where the least m which works is $\text{(k+1)}{}^2\text{4}$ (k odd),$\text{k(k+2)}\text{4}$ (k even).     

Note on lower bounds for the rank of a matrix

The following results are proved: Let A = (a_ij) be an n × n complex matrix, n ? 2, and let k be a fixed integer, 1 ? k ? n ? 1.(1) If there exists a monotonic G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1. (2) If A is irreducible and if there exists a G-function f = (f₁,…,f_n) such that for every subset of S of {1,…,n} consisting of k + 1 elements we have

$\text{Π}\text{i∈S}\text{f}{}_{\mathrm{i}}\text{(A)<}\text{Π}\text{i∈S}\text{|a}{}_{\mathrm{ii}}\text{|,}$

then the rank of A is ? n ? k + 1 if k ? 2, n ? 3; it is ? n ? 1 if k = 1.     

On a conjecture by D. Ž. D̄okovic

It is shown that if $\text{A?Ω}{}_{\mathrm{n}}\text{?{J}{}_{\mathrm{n}}\text{}}$ satisfies

$\text{nkσ}{}_{\mathrm{k}}\text{(A)?(n?k+1)}{}^2\text{σ}{}_{\mathrm{k?1}}\text{(A)}$

$\text{(k=1,2,…,n)}$

, where σ_k(A) denotes the sum of all kth order subpermanent of A, then Per[λJ_n+(1?λ)A] is strictly decreasing in the interval 0<λ<1.     

On the convergence of the Neumann series in interval analysis

Let $\text{A}$ be a real or complex n × n interval matrix. Then it is shown that the Neumann series $\text{Σ}{}^{\mathrm{\infty }}{}_{\mathrm{k=0}}\text{A}{}^{\mathrm{k}}$ is convergent iff the sequence {$\text{A}$^k} converges to the null matrix $\text{O}$, i.e., iff the spectral radius of the real comparison matrix $\text{B}$ constructed in [2] is less than one.     

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)}$

.     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

Commutative algebras of minimal rank

If $\text{A}$ is a finite-dimensional associative k-algebra with unit, then its rank R($\text{A}$), i.e. its bilinear complexity, is never less than $\text{2dim}\text{A}\text{?\#}\text{M}\text{(}\text{A}\text{)}$. $\text{A}$ is said to be of minimal rank if $\text{R(}\text{A}\text{)=2dim}\text{A}\text{?\#}\text{M}\text{(}\text{A}\text{)}$. In this paper we determine for infinite perfect fields k all commutative k-algebras of minimal rank. Roughly speaking, these algebras are built up from simply generated structures which annihilate each other. Furthermore, we indicate how this result can be used to obtain new lower bounds for the rank of specific commutative algebras.     

An intersection problem whose extremum is the finite projective space

Suppose that $\text{A}$ is a finite set-system of N elements with the property |A ∩ A′| = 0, 1 or k for any two different A, A′ ?A. We show that for N > k¹⁴

$\text{|a|=?}\text{N(N?1)(N?k)}\text{(k}{}^2\text{?k+1)(k}{}^2\text{?2k+1)}\text{+}\text{N(N?1)}\text{k(k?1)}\text{+N+1}$

where equality holds if and only if k = q + 1 (q is a prime power) $\text{N =}\text{(q}{}^{\mathrm{t+1}}\text{? 1)}\text{(q ? 1)}$ and $\text{A}$ is the set of subspaces of dimension at most two of the t-dimensional finite projective space of order q.     

On a problem of Katona on minimal completely separating systems with restrictions

Let S be a set of n elements, and k a fixed positive integer $\text{<}\text{1}\text{2}\text{n}$. Katona's problem is to determine the smallest integer m for which there exists a family $\text{A}$ = {A₁, …, A_m} of subsets of S with the following property: |_i| ? k (i = 1, …, m), and for any ordered pair x_i, x_i ∈ S (i ≠ j) there is A₁ ∈ $\text{A}$ such that x_i ∈ A₁, x_j ? A₁. It is given in this note that $\text{m = ?}\text{2n}\text{k}\text{?}\text{if}\text{1}\text{2}\text{k}{}^2\text{? 2}$.     

The covering problem for the fields Q(−1)12 and Q(−3)12

Let k be a positive square free integer, $\text{N(?k)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ the ring of algebraic integers in $\text{Q(?k)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ and S the unit sphere in C_n, complex n-space. If A₁,…, A_n are n linearly independent points of C_n then L = {u₁Au + … + u_nA_n} with $\text{u}{}_{\mathrm{r}}\text{∈ N(?k)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ is called a k-lattice. The determinant of L is denoted by d(L). If L is a covering lattice for S, then $\text{θ(S, L) =}\text{V(S)}\text{d(L)}$ is the covering density. L is called locally (absolutely) extreme if θ(S, L) is a local (absolute) minimum. In this paper we determine unique classes of extreme lattices for k = 1 and k = 3.     

On the van der Waerden conjecture and zeros of polynomials

Let

$\text{F(x) =}\text{∑}\text{k=o}\text{n}\text{n}\text{k}\text{A}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}$

$\text{A}{}_{\mathrm{n}}\text{≠ 0,}$

and

$\text{G(x) =}\text{∑}\text{k=o}\text{n}\text{n}\text{k}\text{B}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}$

$\text{B}{}_{\mathrm{n}}\text{≠ 0,}$

be polynomials with real zeros satisfying A_n?1 = B_n?1 = 0, and let

$\text{H(x) =}\text{∑}\text{k=o}\text{n-2}\text{n}\text{k}\text{A}{}_{\mathrm{k}}\text{B}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k}}\text{.}$

Using the recently proved validity of the van der Waerden conjecture on permanents, some results on the real zeros of H(x) are obtained. These results are related to classical results on composite polynomials.     

On the convergence of powers of interval matrices

We give a necessary and sufficient condition for the sequence {$\text{A}$^k}of the powers of an interval matrix $\text{A}$ to converge to the null matrix $\text{O}$. We construct a point matrix $\text{B}$ which has spectral radius ? ($\text{B}$) less than one if {$\text{A}$^k}converges.