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.     

Complexity of representation of graphs by set systems

Let $\text{F}$ be a family of subsets of S and let G be a graph with vertex set $\text{V={x}{}_{\mathrm{A}}\text{|A ∈}\text{F}\text{}}$ such that: (x_A, x_B) is an edge iff $\text{A?B≠}\text{0}\text{/}$. The family $\text{F}$ is called a set representation of the graph G.It is proved that the problem of finding minimum k such that G can be represented by a family of sets of cardinality at most k is NP-complete. Moreover, it is NP-complete to decide whether a graph can be represented by a family of distinct 3-element sets.The set representations of random graphs are also considered.     

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

Toeplitz matrices and determinants with Fisher-Hartwig symbols

If A and B are self-adjoint operators, this paper shows that A and B have order isomorphic invariant subspace lattices if and only if there are Borel subsets E and F of σ(A) and σ(B), respectively, whose complements have spectral measure zero, and there is a bijective function φ: E → F such that (i) Δ is a Borel subset of E if and only if φ(Δ) is a Borel subset of F; (ii) a Borel subset Δ of E has A-spectral measure zero if and only if φ(Δ) has B-spectral measure zero; (iii) B is unitarily equivalent to φ(A). If A is any self-adjoint operator, there is an associated function κ_A : $\text{N}$ ∪ {∞} → ($\text{N}$ ∪ {0, ∞}) × {0,1} defined in this paper. If $\text{F}$ denotes the collection of all functions from $\text{N}$ ∪ {∞} into ($\text{N}$ ∪ {0,∞}) × {0,1}, then $\text{F}$ is a parameter space for the isomorphism classes of the invariant subspace lattices of self-adjoint operators. That is, two self-adjoint operators A and B have isomorphic invariant subspace lattices if and only if κ_A = κ_B. The paper ends with some comments on the corresponding problem for normal operators.     

Répartition des densités des sous-suites d'une suite d'entiers

Let $\text{A}$ denote a strictly increasing sequence of integers; for any integer n, define A(n) to be the number of positive elements of $\text{A}$ not exceeding n. The upper and lower asymptotic densities of $\text{A}$ are defined by

We describe the set of pairs (d$\text{B}$, $\text{d}$$\text{B}$), where $\text{B}$ runs over all subsequences of $\text{A}$, as being a closed convex region of the plane. The converse statement is also proved.     

A note on polynomial matrix functions over a finite field

Let F_n denote the ring of n×n matrices over the finite field F=GF(q) and let A(x)=A_Nx^N+ ?+ A₁x+A₀?F_n[x]. A function $\text{?:F}{}_{\mathrm{n}}\text{→F}{}_{\mathrm{n}}$ is called a right polynomial function iff there exists an A(x)?F_n[x] such that $\text{?(B)=A}{}_{\mathrm{N}}\text{B}{}^{\mathrm{N}}\text{+?+A}{}_1\text{B+ A}{}_0$ for every B?F_n. This paper obtains unique representations for and determines the number of right polynomial functions.     

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

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

Continuity of positive functionals on topological 1-algebras

It is shown that the set $\text{C}$_{m × n} of complex m × n matrices forms a lower semilattice under the partial ordering A ? B defined by $\text{A}{}^1\text{A = A}{}^1\text{B,}{}^1\text{AA}{}^1\text{= BA}{}^1\text{,}\text{where}\text{A}{}^1$ denotes the conjugate transpose of A. As a special case of a result for division rings, it is further shown that, over any field F, form = n = 2 and any proper involution 1 of F_{2 × 2}, the corresponding intersections A ∩ B all exist.     

On intersecting families of finite sets

Let X = [1, n] be a finite set of cardinality n and let $\text{F}$ be a family of k-subsets of X. Suppose that any two members of $\text{F}$ intersect in at least t elements and for some given positive constant c, every element of X is contained in less than c |$\text{F}$| members of $\text{F}$. How large |$\text{F}$| can be and which are the extremal families were problems posed by Erdös, Rothschild, and Szemerédi. In this paper we answer some of these questions for n > n₀(k, c). One of the results is the following: let $\text{t = 1,}\text{3}\text{7}\text{< c <}\text{1}\text{2}$. Then whenever $\text{F}$ is an extremal family we can find a 7-3 Steiner system $\text{B}$ such that $\text{F}$ consists exactly of those k-subsets of X which contain some member of $\text{B}$.     

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.     

Computing the boxicity of a graph by covering its complement by cointerval graphs

If $\text{F}$ is a family of sets, its intersection graph has the sets in $\text{F}$ as vertices and an edge between two sets if and only if they overlap. This paper investigates the concept of boxicity of a graph G, the smallest n such that G is the intersection graph of boxes in Euclidean n-space. The boxicity, b(G), was introduced by Roberts in 1969 and has since been studied by Cohen, Gabai, and Trotter. The concept has applications to niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. These applications will be described briefly. While the problem of computing boxicity is in general a difficult problem (it is NP-complete), this paper develops techniques for computing boxicity which give useful bounds. They are based on the simple observation that b(G)≤k if and only if there is an edge covering of $\text{G}$ by spanning subgraphs of $\text{G}$, each of which is a cointerval graph, the complement of an interval graph (a graph of boxicity ≤1.).     

Corresponding residue systems in normal extensions

Let K and K′ be number fields with L = K · K′ and F = KφK′. Suppose that $\text{K}\text{F}$ and $\text{K′}\text{F}$ are normal extensions of degree n. Let $\text{B}$ be a prime ideal in L and suppose that $\text{B}$ is totally ramified in $\text{K}\text{F}$ and in $\text{K′}\text{F}$. Let π be a prime element for $\text{B}$_K = $\text{B}$ φ K, and let f(x) ∈ F[x] be the minimum polynomial for π over F. Suppose that $\text{B}$_K · $\text{D}$_L = ($\text{B}$^≠)^e. Then,

$\text{M(B\# : K, K′) =}\text{min}\text{{m, e(t + 1)}}$

, where $\text{t =}\text{min}\text{{t(}\text{K}\text{F}\text{), t(}\text{K′}\text{F}\text{)}}$ and m is the largest integer such that ($\text{B}$_K′)^nm/e φ f($\text{D}$_K′) ≠ {φ}.If we assume in addition to the above hypotheses that [K : F] = [K′: F] = pⁿ, a prime power, and that $\text{B}$ divides p and is totally ramified in $\text{L}\text{F}$, then

$\text{M(B\# : K, K′) ? p}{}^{\mathrm{n?1}}\text{[(p ? 1)(t + p]}$

, with t = t($\text{B}$ : L/F).     

Interpolation by type I factors and the flip automorphism

Given two von Neumann algebras $\text{A}$ ?$\text{B}$ we study the relation between the existence of an interpolating type I factor $\text{F}$, namely $\text{A}$ ?$\text{F}$ ?$\text{B}$, the implementability of the flip automorphism of $\text{A}$ ? $\text{A}$ by a unitary in $\text{B}$ ? $\text{B}$, and the statistical independence of $\text{A}$ and $\text{B}$′ ($\text{A}$ and $\text{B}$′ generate a $\text{W}$¹-tensor product). As an application in Q.F.T. we derive in a natural way a structure theorem of Buchholz for the von Neumann algebras of local observables associated to free fields.     

On the semi-definiteness of the real pencil of two Hermitian matrices

Let A and B be two n×n real symmetric matrices. A theorem of Calabi and Greub-Milnor states that if n?3 and A and B satisfy the condition

$\text{(uAu′)}{}^2\text{+ (uBu′)}{}^2\text{≠ 0}$

for all nonzero vectors u, then there is a linear combination of A and B that is definite. In this note, the author proves two theorems of the semi-definiteness of a nontrivial linear combination of A and B by replacing the condition (¹) by another condition. One of these theorems is a generalization of the theorem of Greub-Milnor and Calabi.     

A global genericity theorem for bifurcations in variational problems

Let C be a Banach space, H a Hilbert space, and let F(C,H) be the space of C^∞ functions f: C × H → R having Fredholm second derivative with respect to x at each (c, x) ?C × H for which $\text{D?}{}_{\mathrm{c}}\text{(x) = 0}$; here we write $\text{?}{}_{\mathrm{c}}\text{(x)}$ for $\text{?(c, x)}$. Say ? is of standard type if at all critical points of ?_c it is locally equivalent (as an unfolding) to a quadratic form Q plus an elementary catastrophe on the kernel of Q. It is proved that if f?F (A × B, H) satisfies a certain ‘general position’ condition, and dim B ? 5, then for most a?A the function f_o?F(B,H) is of standard type. Using this it is shown that those f?F(B,H) of standard type form an open dense set in F(B,H) with the Whitney topology. Thus both results are Hilbert-space versions of Thom's theorem for catastrophes in $\text{R}$ⁿ.     

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.     

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.     

Balancing signed graphs

A signed graph based on F is an ordinary graph F with each edge marked as positive or negative. Such a graph is called balanced if each of its cycles includes an even number of negative edges. Psychologists are sometimes interested in the smallest number d=d(G) such that a signed graph G may be converted into a balanced graph by changing the signs of d edges. We investigate the number D(F) defined as the largest d(G) such that G is a signed graph based on F. We prove that $\text{1}\text{2}\text{m?}\text{nm}\text{≤D(F)≤}\text{1}\text{2}\text{m}$ for every graph F with n vertices and m edges. If F is the complete bipartite graph with t vertices in each part, then $\text{D(F)≤}\text{1}\text{2}\text{t}{}^2\text{?ct}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}$ for some positive constant c.     

Generating the alternating group by cyclic triples

It is shown that a collection of circular permutations of length three on an n-set generates the alternating group A_n if and only if the associated graph is connected. It follows that [$\text{1}\text{2}\text{n}$] circular permutations of length three may generateA_n.