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.     

On the Schur multiplier norm of matrices

The Schur product of two n×n complex matrices A=(a_ij), B=(b_ij) is defined by A°B=(a_ijb_ij. By a result of Schur [2], the algebra of n×n matrices with Schur product and the usual addition is a commutative Banach algebra under the operator norm (the norm of the operator defined on $\text{C}$ⁿ by the matrix). For a fixed matrix A, the norm of the operator B?A°B on this Banach algebra is called the Schur multiplier norm of A, and is denoted by ∥A∥^m. It is proved here that $\text{∥A∥=∥U}{}^1\text{AU∥}{}_{\mathrm{m}}$ for all unitary U (where ∥·∥ denotes the operator norm) iff A is a scalar multiple of a unitary matrix; and that ∥A∥_m=∥A∥ iff there exist two permutations P, Q, a p×p (1?p?n) unitary U, an (n?p)×(n?p)1 contraction C, and a nonnegative number λ such that

$\text{A=λP}\text{U}\text{0}\text{0}\text{C}\text{Q;}$

and this is so iff $\text{∥A°}\text{A}\text{?}\text{∥=∥A∥}{}^2$, where ā is the matrix obtained by taking entrywise conjugates of A.     

A note on matrix subalgebras containing a full Jordan block

Let A be a subalgebra of the full matrix algebra M_n(F), and suppose J∈A, where J is the Jordan block corresponding to xⁿ. Let $\text{S}$ be a set of generators of A. It is shown that the graph of $\text{S}$ determines whether A is the full matrix algebra M_n(F).     

Parallel calculation of a linear mapping on a computer network

We are interested in the parallel computation of a linear mapping of n real variables by a network of computers with restricted means of communication between them and without any common memory. Let $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ denote the algebra of n×n real matrices, and let G be the graph associated with a binary, reflexive and symmetric relation R over {1,2, …,n}. We define

$\text{A}{}_{\mathrm{R}}\text{= {A?M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{):a}{}_{\mathrm{ij}}\text{≠ 0}\text{implies}\text{iRj}}$

A matrix $\text{M∈M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ is said to be realizable on G if it can be expressed as a product of elements of A_R. Therefore, every matrix of $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ is realizable on G if and only if A_R generates $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$. We show that A_R generates $\text{M}{}_{\mathrm{n\times n}}\text{(}\text{R}\text{)}$ if and only if G is connected.     

Fast canonization of circular strings

A circular string A = (a₁,…,a_n) is a string that has n equivalent linear representations A_i = a_i,…,a_n,a₁,…,a_i?1 for i = 1,…,n. The a_i's are assumed to be well ordered. We say that A_i < A_j if the word a_i…a_na₁…a_i?1 precedes the word a_j…a_na₁…a_j?1 in the lexicographic order, A_i ? A_j if either A_i < A_j or A_i = A_j. A_i0 is a minimal representation of A if A_i0 ? A_i for all 1 ≤ i ≤ n. The index i₀ is called a minimal starting point (m.s.p.). In this paper we discuss the problem of finding m.s.p. of a given circular string. Our algorithm finds, in fact, all the m.s.p.'s of a given circular string A of length n by using at most $\text{n + ?}\text{d}\text{2}\text{?}$ comparisons. The number d denotes the difference between two successive m.s.p.'s (see Lemma 1.1) and is equal to n if A has a unique m.s.p. Our algorithm improves the result of 3n comparisons given by K. S. Booth. Only constant auxiliary storage is used.     

An extremal problem among subsets of a set

We determine the maximum size of a family of subsets in {1, 2,…, n} with the property that if A₁, A₂, A₃,… are any members of the family with $\text{∩A}{}_{\mathrm{i}}\text{= ?}$, then ∪A_i = {1, 2,…, n}.     

Bounds for the uniform deviation of empirical measures

If X₁,…,X_n are independent identically distributed R^d-valued random vectors with probability measure μ and empirical probability measure μ_n, and if $\text{a}$ is a subset of the Borel sets on R^d, then we show that P{sup_{A∈$\text{a}$}|μ_n(A)?μ(A)|≥ε} ≤ cs($\text{a}$, n²)e^?2n∈2, where c is an explicitly given constant, and s($\text{a}$, n) is the maximum over all (x₁,…,x_n) ∈ R^dn of the number of different sets in {{x₁…,x_n}∩A|A ∈$\text{a}$}. The bound strengthens a result due to Vapnik and Chervonenkis.     

On positional games

Let {A_i} be a family of sets and let S = ∩_iA_i. By a positional game we shall mean a game played by two players on {A_i}. The players alternately pick elements of S and that player wins who fist has all the elements of one of the A_i. This paper deals with almost disjoint hypergraphs only, i.e., |A_i∪A_j| ? 1 if i ≠ j. Let $\text{M}{}^1\text{(n)}$ be the smallest integer for which there is an almost disjoint n-uniform hypergraph $\text{|T| = M}{}^1\text{(n)}$, so that the first player has a winning strategy. It is shown that $\text{lim}{}_{\mathrm{n}}\text{[M}{}^1\text{(n)]}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 4}$, which was conjectured by Erdös. The same method is applied to prove a conjecture of Hales and Jewett on r-dimensional tick-tack-toe if r is large enough. Finally we prove that for an arbitrary almost disjoint n-uniform hypergraph the second player has such a strategy that the first player unable to win in his mth move if m < (2 ? ?)ⁿ.     

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.     

A covering theorem for quasi-groups

It is shown that if Q is a quasi-group of order n and k is moderately large, there exists a subset A of Q of size k such that if t is the least number of left translates of A needed to cover Q, then $\text{t >}\text{c(n}\text{log}\text{n)}\text{k}$.     

Sperner systems consisting of pairs of complementary subsets

It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if $\text{A}$ = {;A₁,…, A_l}; consists of k-subsets of a set with n > 2k elements such that A_i ∩ A_j ≠ ? for all i, j then l ? (_k?1^n?1). Schönheim proved that if A₁, …, A_l are subsets of a set S with n elements such that A_i ? A_j, A_i ∩ A_j ≠ ø and A_i ∪ A_j ≠ S for all i ≠ j then $\text{l ? (}{}_{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]\; ?\; 1</mtext>}}{}^{\mathrm{n\; ?\; 1}}\text{)}$. In this note we prove a common strengthening of these results.     

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.     

Permanental Polytopes of Doubly Stochastic Matrices

A subpolytope Γ of the polytope Ω_n of all n×n nonnegative doubly stochastic matrices is said to be a permanental polytope if the permanent function is constant on Γ. Geometrical properties of permanental polytopes are investigated. No matrix of the form 1⊕A where A is in Ω₂ is contained in any permanental polytope of Ω₃ with positive dimension. There is no 3-dimensional permanental polytope of Ω₃, and there is essentially a unique maximal 2-dimensional permanental polytope of Ω₃ (a square of side $\text{1}\text{3}$). Permanental polytopes of dimension $\text{(n}{}^2\text{?3n+4)}\text{2}$ are exhibited for each n?4.     

p-Minors of a doubly stochastic matrix at which the permanent achieves a minimum

The author proves that if A is a matrix at which the permanent achieves a local minimum relative to the set of n x n doubly stochastic matrices, then for a_ij=0,

$\text{per A (i|j)?per A}$

.     

On matrices having equal corresponding principal minors

Let A, B be n × n matrices with entries in a field F. We say A and B satisfy property $\text{D}$ if B or B^t is diagonally similar to A. It is clear that if A and B satisfy property $\text{D}$, then they have equal corresponding principal minors, of all orders. The question is to what extent the converse is true. There are examples which show the converse is not always true. We modify the problem slightly and give conditions on a matrix A which guarantee that if B is any matrix which has the same principal minors as A, then A and B will satisfy property $\text{D}$. These conditions on A are formulated in terms of ranks of certain submatrices of A and the concept of irreducibility.     

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

On ranges of Lyapunov transformations

A Lyapunov transformation is a linear transformation on the set $\text{H}$_n of hermitian matrices H ? $\text{C}$^n,n of the form $\text{L}$_A(H) = A¹H + HA, where A ?$\text{C}$^n,n. Given a positive stable A ?$\text{C}$^n,n, the Stein-Pfeffer Theorem characterizes those K ? $\text{H}$_n for which K = $\text{L}$_B(H), where B is similar to A and H is positive definite. We give a new proof of this result, and extend it in several directions. The proofs involve the idea of a controllability subspace, employed previously in this context by Snyders and Zakai.     

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 Minimum Value of the Permanent of a Nearly Decomposable Doubly Stochastic Matrix

Let A be a minimizing matrix for the permanent over the face of Ω_n determined by a fully indecomposable matrix. It is shown that A is fully indecomposable and positive elements of A have permanental minors equal to per(A). Furthermore a zero entry of A has its permanental minor greater than or equal to per(A), provided that same element of the face has its corresponding entry positive. For 2?n?9 the minimum value of the permanent of a nearly decomposable $\text{A∈Ω}{}_{\mathrm{n}}$ is $\text{1}\text{2}{}^{\mathrm{n-1}}$.     

Applications of the Connes spectrum to C1-dynamical systems,II

We show that for a C¹-dynamical system (A, G, α) with G discrete (abelian) the Connes spectrum Γ(α) is equal to $\text{G}\text{?}$ if and only if every nonzero closed ideal in G × _αA has a nonzero intersection with A. Denote by G_J the closed subgroup of G that leaves fixed the primitive ideal J of A. We show for a general group G that if all isotropy groups G_J are discrete, then GX_αA is simple if and only if A is G-simple and $\text{Γ(}\text{α}\text{) =}\text{G}\text{?}$. This result is applicable not only when G is discrete but also when G?$\text{R}$ or G?$\text{T}$ provided that A is not primitive. Specializing to single automorphisms (i.e., G=$\text{Z}$) we show that if (the transposed of) α acts freely on a dense set of points in $\text{A}\text{?}$, then Λ(α)=$\text{T}$. The converse is only proved when A is of type I.