On the accuracy of the Gerschgorin circle theorem for bounding the spread of a real symmetric matrix

The spread of a matrix with real eigenvalues is the difference between its largest and smallest eigenvalues. The Gerschgorin circle theorem can be used to bound the extreme eigenvalues of the matrix and hence its spread. For nonsymmetric matrices the Gerschgorin bound on the spread may be larger by an arbitrary factor than the actual spread even if the matrix is symmetrizable. This is not true for real symmetric matrices. It is shown that for real symmetric matrices (or complex Hermitian matrices) the ratio between the bound and the spread is bounded by $\text{p+1}$, where p is the maximum number of off diagonal nonzeros in any row of the matrix. For full matrices this is just $\text{n}$. This bound is not quite sharp for n greater than 2, but examples with ratios of $\text{n?1}$ for all n are given. For banded matrices with m nonzero bands the maximum ratio is bounded by $\text{m}$ independent of the size of n. This bound is sharp provided only that n is at least 2m. For sparse matrices, p may be quite small and the Gerschgorin bound may be surprisingly accurate.     

On decomposition of r-partite graphs into edge-disjoint hamilton circuits

Let K(n;r) denote the complete r-partite graph K(n, n,…, n). It is shown here that for all even n(r ? 1) ? 2, K(n;r) is the union of $\text{n(r ? 1)}\text{2}$ of its Hamilton circuits which are mutually edge-disjoint, and for all odd n(r ? 1) ? 1, K(n;r) is the union of $\text{(n(r ? 1) ? 1)}\text{2}$ of its Hamilton circuits and a 1-factor, all of which are mutually edge-disjoint.     

Rational matrix groups of a special type

Let G be a finite group having a faithful irreducible character χ for which χ(1) is prime to ¦G¦/χ(1). Let n=[$\text{Q}$(χ):$\text{Q}$]χ(1), and assume that the factors are not both even. Then G can be embedded in GL_n($\text{Q}$) in such a way that its normalizer therein splits over its centralizer.     

Coverings of the complete (di-)graph with n vertices by complete bipartite (di-)graphs with n vertices I

Let n be an integer, n ? 2. A set $\text{M}$_n of complete bipartite (di-)graphs with n vertices is called a critical covering of the complete (di-)graph with n vertices if and only if the complete (di-)graph is covered by the (di-)graphs of $\text{M}$_n, but of no proper subset of $\text{M}$_n. All possible cardinalities of critical coverings $\text{M}$_n are determined for all integers n and for undirected as well as directed graphs.     

On a set puncturing problem

It is established that the maximum number of points required to puncture 3n sets of probability $\text{2}\text{3n}$ is 2n, as had been conjectured. In fact, for 1 ≤ m ≤ n, a family of m sets of probability $\text{2}\text{n}$ can be punctured using no more than $\text{min}\text{(m,[}\text{(n + m)}\text{3}\text{])}$ points. The more general statement that (k + 1)n sets of probability $\text{k}\text{(k + 1)n}$ require at most 2n points for puncturing is shown to be false already for k = 3.     

Extreme points in sets of positive linear maps on B(H)

Three main results are obtained: (1) If $\text{D}$ is an atomic maximal Abelian subalgebra of $\text{B}$($\text{H}$), $\text{P}$ is the projection of $\text{B}$($\text{H}$) onto $\text{D}$ and h is a complex homomorphism on $\text{D}$, then h ° $\text{P}$ is a pure state on $\text{B}$($\text{H}$). (2) If {P_n} is a sequence of mutually orthogonal projections with rank(P_n) = n and ∑ P_n = I, $\text{P}$ is the projection of $\text{B}$($\text{H}$) onto {P_n}″ given by P(T)=∑trace_n(T)P_n and h is a homomorphism on {P_n}″ such that h(P_n) = 0 for all n then h ° $\text{P}$ induces a type II_∞ factor representation of the Calkin algebra. (3) If $\text{M}$ is a nonatomic maximal Abelian subalgebra of $\text{B}$($\text{H}$) then there is an atomic maximal Abelian subalgebra $\text{D}$ of $\text{B}$($\text{H}$) and a large family {Φ_α} of ¹-homomorphisms from $\text{D}$ onto $\text{M}$ such that for each α, Φ_α ° $\text{P}$ is an extreme point in the set of projections from $\text{B}$($\text{H}$) onto $\text{M}$. (Here $\text{P}$ denotes the projection of $\text{B}$($\text{H}$) onto $\text{D}$.)     

Completing partial latin squares

It is shown that if a partial latin square of order n with fewer than n entries has all its entries in no more than $\text{(n + 3)}\text{2}$ rows, then it can be completed. This extends previous results of both Lindner and Wells, but lately Wells has improved this to $\text{(n + 5)}\text{2}$. We show that the number $\text{(n + 3)}\text{2}$ is the best obtainable by the method of completing one row at a time without regard for completing future rows.     

Finding the maximum,merging, and sorting in a parallel computation model

A model for synchronized parallel computation is described in which all p processors have access to a common memory. This model is used to solve the problems of finding the maximum, merging, and sorting by p processors. The main results are: 1. Finding the maximum of n elements (1 < p ≤ n) within a depth of $\text{O(}\text{n}\text{p}\text{+}\text{log log}\text{p)}$; (optimal for $\text{p ≤}\text{n}\text{log log}\text{n}$). 2. Merging two sorted lists of length m and n (m ≤ n) within a depth of $\text{O(}\text{n}\text{p}\text{+}\text{log}\text{n)}$ for p ≤ n (optimal for $\text{p ≤}\text{n}\text{log}\text{n}$), $\text{O(}\text{log}\text{m}\text{log}\text{p}\text{n}\text{)}$ for $\text{p ≥ n(= O(k)}\text{if}\text{p = m}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{n, k > 1)}$. 3. Sorting n elements within a depth of $\text{O(}\text{n}\text{p}\text{log}\text{n}\text{+}\text{log}\text{n}\text{log}\text{p)}$ for p ≤ n, (optimal for $\text{p ≤}\text{n}\text{log}\text{n}$). $\text{O(}\text{log}{}^2\text{n}\text{log}\text{p}\text{n}\text{) +}\text{log}\text{n)}$ for $\text{p ≥ n (= O(k}\text{log}\text{n)}\text{if}\text{p = n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{, k > 1)}$. The depth of O(klogn) for $\text{p = n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ processors was also achieved by Hirschberg (Comm. ACM21, No. 8 1978, 657–661) and Preparata IEEE Trans ComputersC-27 (July 1978), 669–673). Our algorithm is substantially simpler. All the elementary operations including allocation of processors to their jobs are taken into account in deriving the depth complexity and not only comparisons.     

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.     

Convex polyhedra of doubly stochastic matrices: II. Graph of Ωn

Properties of the graph $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ of the polytope $\text{Ω}{}_{\mathrm{n}}$ of all n × n nonnegative doubly stochastic matrices are studied. If $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$ which is not a k-dimensional rectangular parallelotope for k ≥ 2, then G($\text{F}$) is Hamilton connected. Prime factor decompositions of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ relative to Cartesian product are investigated. In particular, if $\text{F}$ is a face of $\text{Ω}{}_{\mathrm{n}}$, then the number of prime graphs in any prime factor decomposition of G($\text{F}$) equals the number of connected components of the neighborhood of any vertex of G($\text{F}$). Distance properties of the graphs of faces of $\text{Ω}{}_{\mathrm{n}}$ are obtained. Faces $\text{F}$ of $\text{Ω}{}_{\mathrm{n}}$ for which G($\text{F}$) is a clique of $\text{G(Ω}{}_{\mathrm{n}}\text{)}$ are investigated.     

Inside the D-stable matrices

Let $\text{DS}{}_{\mathrm{n}}\text{(}\text{F}\text{)}$ denote the set of n×nD-stable matrices with entries from $\text{F}\text{?}\text{C}$. A characterization of the interior of $\text{DS}{}_{\mathrm{n}}\text{(}\text{F}\text{)}$ considered as subset of the topological space $\text{F}$ⁿ², is given for the cases $\text{F}\text{=}\text{R}\text{and}\text{C}$.     

Triangulated n-manifolds are determined by their [n2] + 1-skeletons

We will reconstruct compact, triangulated n-manifolds—without-boundaries from just their $\text{[}\text{n}\text{2}\text{] + 1}$ skeletons. Therefore, two such manifolds are isomorphic if they have simplicially isomorphic $\text{[}\text{n}\text{2}\text{+ 1}$-skeletons. Furthermore, when n is even, and the $\text{n}\text{2}$-homology group is zero, then the $\text{n}\text{2}$-skeleton is sufficient.     

Orientable and nonorientable genus of the complete bipartite graph

K_m,n is the complete bipartite graph with m and n vertices in its chromatic classes. G. Ringel has proved that the orientable genus of K_m,n is equal to $\text{{}\text{(m ? 2)(n ? 2)}\text{4}\text{}}\text{if}\text{m ≥ 2}\text{and}\text{n ≥ 2}$ and that its nonorientable genus is equal to $\text{{}\text{(m ? 2)(n ? 2)}\text{2}\text{}}\text{if}\text{m ≥ 3}\text{and}\text{n ≥ 3}$. We give new proofs of these results.     

Quasi-free derivations on the Canonical Anticommutation Relation algebra

An unbounded 1-derivation δ on a C¹-algebra $\text{U}$ is called approximately bounded if there is an increasing sequence of full matrix subalgebras {$\text{U}$_n} whose union is dense in the domain of $\text{U}$ and a sequence {h_n} of self-adjoint elements of $\text{U}$ such that h_n implements δ on $\text{U}$_n for every n, and {∥h_n ? Q_n(h_n)∥} is a bounded sequence where Q_n is the canonical conditional expectation of $\text{U}$ onto $\text{U}$_n. We prove that a quasi-free derivation on the Canonical Anticommutation Relation algebra is approximately bounded if the self-adjoint operator from which it arises is of finite multiplicity and bounded. We conjecture that all quasi-free derivations are approximately bounded. We also prove that a quasi-free derivation is bounded if and only if the self-adjoint operator from which it arises is of the trace class.     

Some special vapnik-chervonenkis classes

For a class $\text{C}$ of subsets of a set X, let V($\text{C}$) be the smallest n such that no n-element set F?X has all its subsets of the form A ∩ F, A ∈ $\text{C}$. The condition V($\text{C}$) <+∞ has probabilistic implications. If any two-element subset A of X satisfies both A ∩ C = Ø and A ? D for some C, D∈$\text{C}$, then $\text{V(}\text{C}\text{)=2}$ if and only if $\text{C}$ is linearly ordered by inclusion. If $\text{C}$ is of the form $\text{C}\text{={∩}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{C}{}_{\mathrm{i}}\text{:C}{}_{\mathrm{i}}\text{∈}\text{C}{}_{\mathrm{i}}$, i=1,2,…,n}, where each $\text{C}{}_{\mathrm{i}}$ is linearly ordered by inclusion, then $\text{V(}\text{C}\text{)?n+1}$. If H is an (n-1)-dimensional affine hyperplane in an n-dimensional vector space of real functions on X, and $\text{C}$ is the collection of all sets {x: f(x)>0} for f in H, then $\text{V(}\text{C}\text{)=n}$.     

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

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.     

Construction of matroidal families by partly closed sets

A matroidal family of graphs is a set $\text{M}$≠Ø of connected finite graphs such that for every finite graph G the edge sets of those subgraphs of G which are isomorphic to some element of $\text{M}$ are the circuits of a matroid on the edge set of G. In [9], Schmidt shows that, for n?0, ?2n<r?1, n, $\text{r∈}\text{Z}$, the set $\text{M}\text{(n, r)={G∣G}$ is a graph with β(G)=nα(G)+r and α(G )>, and is minimal with this property (with respect to the relation ?))} is a matroidal family of graphs. He also describes a method to construct new matroidal families of graphs by means of so-called partly closed sets. In this paper, an extension of this construction is given. By means of s-partly closed subsets of $\text{M}\text{(n, r)}$, s?r, we are able to give sufficient and necessary conditions for a subset $\text{P}\text{(n, r)}$ of $\text{M}\text{(n, r)}$ to yield a matroidal family of graphs when joined with the set $\text{I}\text{(n, s)}$ of all graphs $\text{G∈}\text{M}\text{(n, s)}$ which satisfy: If $\text{H∈}\text{P}\text{(n, r)}$, then H?G. In particular, it is shown that $\text{M}\text{(n, r)}$ is not a matroidal family of graphs for r?2. Furthermore, for n?0, 1?2n<r, n, $\text{r∈}\text{Z}$, the set of bipartite elements of $\text{M}\text{(n, r)}$ can be used to construct new matroidal families of graphs if and only if s?min(n+r, 1).