Small diameter interchange graphs of classes of matrices of zeros and ones

Let $\text{A}$(R, S) denote the class of all m×n matrices of 0's and 1's having row sum vector R and column sum vector S. The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{A}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We characterize those $\text{A}$(R, S) for which the graph G(R, S) has diameter at most 2 and those $\text{A}$(R, S) for which G(R, S) is bipartite.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

The relationship between the class %plane1D;518;2(R,S) of (0,1,2)-matrices and the collection of constellation matrices

Let %plane1D;518;₂(R,S) be the class of all (0, 1, 2)-matrices with a prescribed row sum vector R and column sum vector S. A (0, 1,2)-matrix in %plane1D;518;₂(R,S) is defined to be parsimonious provided no (0, 1, 2)-matrix with the same row and column sum vectors has fewer positive entries. In a parsimonious (0, 1, 2)-matrix A there are severe restrictions on the (0, 1)-matrix A⁽¹⁾ which records the positions of the 1's in A. Brualdi and Michael obtained some necessary arithmetic conditions for a set of matrices to serve simultaneously as the 1-pattern matrices for parsimonious matrices in a given class. In this paper, we provide a direct construction that proves that these conditions are also sufficient.     

Convergence of a subgradient method for computing the bound norm of matrices

Let φ and ψ be any norms on $\text{R}$^m and $\text{R}$ⁿ respectively. We study a subgradient method for computing the associated bound norm S_φψ(A) = sup{φ(Ax), ψ(x)?1} (a nonconvex optimization problem). It is proved that homodual method converges when one of the norms φ and ψ is polyhedral.     

Decomposition de Km+Kn en cycles hamiltoniens

Let K_m be the complete graph of order m. We prove that the cartesian sum K_m+K_n can be decomposed into $\text{1}\text{2}$(m+n?2) hamiltonian cycles if m+n is even and into $\text{1}\text{2}$(m+n?3) hamiltonian cycles and a perfect matching if m+n is odd.     

Some improvements in Neuberger's iteration procedure for solving partial differential equations

If m and n are positive integers then let S(m, n) denote the linear space over R whose elements are the real-valued symmetric n-linear functions on E_m with operations defined in the usual way. If $\text{U}$ is a function from some sphere S in E_m to R then let $\text{U}$⁽ⁱ⁾(x) denote the ith Frechet derivative of $\text{U}$ at x. In general $\text{U}$⁽ⁱ⁾(x)∈S(m,i). In the paper “An Iterative Method for Solving Nonlinear Partial Differential Equations” [Advances in Math. 19 (1976), 245–265] Neuberger presents an iterative procedure for solving a partial differential equation of the form

$\text{AU}{}^{\mathrm{n}}\text{(x)=F(x, U(x), U′(x),…,U}{}^{\mathrm{k}}\text{(x))}$

, where k > n, $\text{U}$ is the unknown from some sphere in E_m to R, A is a linear functional on S(m, n), and F is analytic. The defect in the theory presented there was that in order to prove that the iterates converged to a solution $\text{U}$ the condition $\text{k ?}\text{n}\text{2}$ was needed. In this paper an iteration procedure that is a slight variation on Neuberger's procedure is considered. Although the condition $\text{k ?}\text{n}\text{2}$ cannot as yet be eliminated, it is shown that in a broad class of cases depending upon the nature of the functional A the restriction $\text{k ?}\text{n}\text{2}$ may be replaced by the restriction $\text{k ?}\text{3n}\text{4}$.     

Projective unitary positive-energy representations of diff (S1)

Let $\text{D}$ be the group of orientation-preserving diffeomorphisms of the circle S¹. Then $\text{D}$ is Fréchet Lie group with Lie algebra (δ_∞)_R the smooth real vector fields on S¹. Let δ_R be the subalgebra of real vector fields with finite Fourier series. It is proved that every infinitesimally unitary projective positive-energy representation of δ_R integrates to a continuous projective unitary representation of $\text{D}$. This result was conjectured by V. Kac.     

On the spectral synthesis problem for hypersurfaces of RN

Let F¹(Rⁿ) denote the Fourier algebra on $\text{R}$ⁿ, and $\text{D}$($\text{R}$ⁿ) the space of test functions on $\text{R}$ⁿ. A closed subset E of $\text{R}$ⁿ is said to be of spectral synthesis if the only closed ideal J in F¹(Rⁿ) which has E as its hull

$\text{h(J)={x ? R}{}^{\mathrm{n}}\text{:f(x)=0}\text{for all}\text{f ? J}}$

is the ideal

$\text{k(E)={f?F}{}^1\text{(R}{}^{\mathrm{n}}\text{):f(E)=0}}$

. We consider sufficiently regular compact subsets of smooth submanifolds of $\text{R}$ⁿ with constant relative nullity. For such sets E we give an estimate of the degree of nilpotency of the algebra $\text{(k(E)∩D(R}{}^{\mathrm{n}}\text{))}{}^{\mathrm{?}}\text{j(E)}$, where j(E) denotes the smallest closed ideal in F¹(Rⁿ) with hull E. Especially in the case of hypersurfaces this estimate turns out to be exact. Moreover for this case we prove that k(E)∩D(Rⁿ) is dense in k(E). Together this solves the synthesis problem for such sets.     

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

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.     

Linear operators preserving the (p,q)-numerical range

Let $\text{C}{}_{\mathrm{n\times n}}$ and $\text{H}{}_{\mathrm{n}}$ denote respectively the space of n×n complex matrices and the real space of n×n hermitian matrices. Let p,q,n be positive integers such that p?q?n. For $\text{A?}\text{C}{}_{\mathrm{n\times n}}$, the (p,q)-numerical range of A is the set

$\text{W}{}_{\mathrm{p,q}}\text{(A)={trC}{}_{\mathrm{p}}\text{(J}{}_{\mathrm{q}}\text{UAU}{}^1\text{):U}\text{unitary}\text{}}$

, where C_p(X) is the pth compound matrix of X, and Jq is the matrix I_q?O_n-q. Let $\text{L}$ denote $\text{H}$_n or $\text{C}{}_{\mathrm{n\times n}}$. The problem of determining all linear operators T: $\text{L}$→$\text{L}$ such that

$\text{W}{}_{\mathrm{p,q}}\text{(T(A))=W}{}_{\mathrm{p,q}}\text{(A)}\text{for all}\text{A?}\text{L}$

is treated in this paper.     

Duality between some linear preserver problems. II. Isometries with respect to c-special norms and matrices with fixed singular values

Let $\text{F}{}_{\mathrm{m\times n}}$ (m?n) denote the linear space of all m × n complex or real matrices according as $\text{F}$=$\text{C}$ or $\text{R}$. Let c=(c₁,…,c_m)≠0 be such that c₁???c_m?0. The c-spectral norm of a matrix A?$\text{F}$_m×n is the quantity

$\text{6A6}{}_{\mathrm{c}}\text{∑}\text{i=I}\text{m}\text{c}{}_{\mathrm{i}}\text{σ}{}_{\mathrm{i}}\text{(A)}$

. where σ₁(A)???σ_m(A) are the singular values of A. Let d=(d₁,…,d_m)≠0, where d₁???d_m?0. We consider the linear isometries between the normed spaces $\text{(}\text{F}{}_{\mathrm{m\times }}{}_{\mathrm{n}}\text{,∥·∥}{}_{\mathrm{<mtext>c</mtext>}}\text{)}$ and $\text{(}\text{F}{}_{\mathrm{m\times }}{}_{\mathrm{n}}\text{,∥·∥}{}_{\mathrm{d}}\text{)}$, and prove that they are dual transformations of the linear operators which map $\text{L}$(d) onto $\text{L}$(c), where

$\text{L}\text{(c)= {X?}\text{F}{}_{\mathrm{m\times n}}\text{:X}\text{has singular values}\text{c}{}_1\text{,…,c}{}_{\mathrm{m}}\text{}}$

.     

SOME PROPERTIES OF A CLASS OF INTERCHANGE GRAPHS

§１ＩｎｔｒｏｄｕｃｔｉｏｎＬｅｔＧｂｅａｃｏｎｎｅｃｔｅｄｇｒａｐｈｗｉｔｈｖｅｒｔｅｘ－ｓｅｔＶ（Ｇ）ａｎｄｅｄｇｅ－ｓｅｔＥ（Ｇ）．Ｄｅｎｏｔｅｂｙｅ＝（ｘ，ｙ）ｔｈｅｅｄｇｅｊｏｉｎｉｎｇｔｈｅｖｅｒｔｉｃｅｓｘａｎｄｙｏｆＧ．Ａｍ－ｃｌｉｑ...     

The isometries of LP(Ω, X)

Let (Ω, ∑, μ) be a finite measure space and X a separable Banach space. We characterize the linear isometries of $\text{L}{}^{\mathrm{p}}\text{(Ω, X)}$ onto itself for 1 ? p < ∞, p ≠ 2 under the condition that X is not the l^p-direct sum of two nonzero spaces (for the same p). It is shown that T is such an isometry if and only if (Tf)(·) = S(·)h(·)(Φ(f))(·), where Φ is a set isomorphism of ∑ onto itself, S is a strongly measurable operator-valued map such that S(t) is a.e. an isometry of X onto itself, and h is a scalar function which is related to Φ. It is further shown that for a big class of measure spaces (perhaps all nontrivial ones) the condition on X is also a necessary condition for the above conclusion to hold. In the case when X is a Hilbert space the injective isometries of $\text{L}{}^{\mathrm{p}}\text{(Ω, X)}$ are also characterized. They have the same form as above, except that Φ and S(t) are not necessarily onto.     

On the rate of convergence in the central limit theorem and the type of the Banach space

Let E be a Banach space. Let ξ be a sequence of which goes to zero. Let X be a centered E-valued random variable, which is bounded. Let S_n be the sum of n independent copies of X. Assume that whenever X satisfies the CLT, we have.

$\text{Sup}\text{t ?R}\text{|P(}\text{6S}{}_{\mathrm{n}}\text{√n | ? t}\text{) ? μ ({x;6x6 ?})| ? ξ}{}_{\mathrm{n}}$

where μ is the (Gaussian) limit of the laws of S_n. Then E is type 2.     

Rank-k-preservers and preservers of sets of ranks

Let T be a linear transformation on the set of m × n matrices with entries in an algebraically closed field. If T maps the set of all matrices whose rank is k into itself, and if$\text{n?}\text{3}\text{k}\text{2}$, then the rank of A is the rank of T(A) for every m × n matrix.     

Injectivity and operator spaces

Let B(H) be the bounded operators on a Hilbert space H. A linear subspace R ? B(H) is said to be an operator system if 1 ?R and R is self-adjoint. Consider the category $\text{b}$ of operator systems and completely positive linear maps. R ∈ $\text{C}$ is said to be injective if given A ? B, A, B ∈ $\text{C}$, each map A → R extends to B. Then each injective operator system is isomorphic to a conditionally complete C¹-algebra. Injective von Neumann algebras R are characterized by any one of the following: (1) a relative interpolation property, (2) a finite “projectivity” property, (3) letting M_m = B(C^m), each map R → N ? M_m has approximate factorizations R → M_n → N, (4) letting K be the orthogonal complement of an operator system N ? M_m, each map $\text{M}{}_{\mathrm{m}}\text{K}\text{→ R}$ has approximate factorizations $\text{M}{}_{\mathrm{m}}\text{K}\text{→ M}{}_{\mathrm{n}}\text{→ R}$. Analogous characterizations are found for certain classes of C¹-algebras.     

Générateurs et semi-groupes dans les espaces de Banach uniformement lisses

Let C be a closed convex subset of a uniformly smooth Banach space. Let S(t) : C → C be a semigroup of type ω. Then the generator A₀ of S(t) has a dense domain in C. Moreover there is is an operator A such that: (i) A₀ ? A and $\text{D(A)}\text{= C, (ii) A + gwI}$ accretive, (iii) R(I + λA) ? C for λ > 0 and ωλ < 1, (iv) $\text{S(t)x =}\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{(I + (}\text{t}\text{n}\text{)A)}{}^{\mathrm{?n}}\text{x}$ for every x?C.     

An analogue of the thom isomorphism for crossed products of a C1 algebra by an action of R

In this paper we show the existence and uniqueness of a natural isomorphism ø^j_α of K_j(A) with K_j+1(A ?_α$\text{R}$), j ? $\text{Z}$/2 where (A, $\text{R}$, α) is a $\text{C1}$ dynamical $\text{R}$-system, K is the functor of topological K theory and A ?_α$\text{R}$ is the crossed product of A by the action of $\text{R}$. The Pimsner-Voiculescu exact sequence is obtained as a corollary. We show that given an α-invariant trace τ on A, with dual trace $\text{}\text{?}$gt, one has $\text{}\text{?}\text{gtø}{}^1{}_{\mathrm{\alpha }}\text{[u] = (}\text{1}\text{2}\text{iπ) τ(δ(u)u1)}$ for any unitary u in the domain of the derivation δ of A associated to the action α. Finally, we show that the crossed product of C(S³) (continuous functions on the 3 sphere) by a minimal diffeomorphism is a simple $\text{C1}$ algebra with no nontrivial idempotent.     

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.