Balancing poset extensions

We show that any finite partially ordered setP (not a total order) contains a pair of elementsx andy such that the proportion of linear extensions ofP in whichx lies belowy is between 3/11 and 8/11. A consequence is that the information theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: ifX is a totally ordered set about which we are given some partial information, and ife(X) is the number of total orderings ofX compatible with this information, then it is possible to sortX using no more thanC log₂ e (X) comparisons whereC is approximately 2.17.Supported in part by NSF Grant MCS83-01867.     

Singular-value-like decomposition for complex matrix triples

The classical singular value decomposition for a matrix A∈C^m×n is a canonical form for A that also displays the eigenvalues of the Hermitian matrices AA^∗ and A^∗A. In this paper, we develop a corresponding decomposition for A that provides the Jordan canonical forms for the complex symmetric matrices and . More generally, we consider the matrix triple , where are invertible and either complex symmetric or complex skew-symmetric, and we provide a canonical form under transformations of the form , where X,Y are nonsingular.     

The convexity lattice of a poset

The authors investigate the lattice Co(P) of convex subsets of a general partially ordered set P. In particular, they determine the conditions under which Co(P) and Co(Q) are isomorphic; and give necessary and sufficient conditions on a lattice L so that L is isomorphic to Co(P) for some P.     

On orthogonal systems of matrix algebras

In this work it is shown that certain interesting types of orthogonal system of subalgebras (whose existence cannot be ruled out by the trivial necessary conditions) cannot exist. In particular, it is proved that there is no orthogonal decomposition of M_n(C)⊗M_n(C)≡M_n²(C) into a number of maximal abelian subalgebras and factors isomorphic to M_n(C) in which the number of factors would be 1 or 3.In addition, some new tools are introduced, too: for example, a quantity c(A,B), which measures “how close” the subalgebras A,B⊂M_n(C) are to being orthogonal. It is shown that in the main cases of interest, c(A^′,B^′) - where A^′ and B^′ are the commutants of A and B, respectively - can be determined by c(A,B) and the dimensions of A and B. The corresponding formula is used to find some further obstructions regarding orthogonal systems.     

Trimmed linearizations for structured matrix polynomials

We discuss the eigenvalue problem for general and structured matrix polynomials which may be singular and may have eigenvalues at infinity. We derive condensed forms that allow (partial) deflation of the infinite eigenvalue and singular structure of the matrix polynomial. The remaining reduced order staircase form leads to new types of linearizations which determine the finite eigenvalues and corresponding eigenvectors. The new linearizations also simplify the construction of structure preserving linearizations.     

A solution to a spectral poset problem of Lewis and Ohm

We show that there is a 1-dimensional (countable) non-spectral poset X such that for all x≠y∈X, ↑x∩↑y and ↓x∩↓y are finite subsets. On the other hand, we obtain some sufficient conditions for posets to be spectral.     

The Frobenius complexity of Hibi rings

We study the Frobenius complexity of Hibi rings over fields of characteristic $p>0$. In particular, for a certain class of Hibi rings (which we call ${\omega }^{(?1)}$-level), we compute the limit of the Frobenius complexity as $p\to \infty$.     

A characterization of Leonard pairs using the notion of a tail

Let V denote a vector space with finite positive dimension. We consider an ordered pair of linear transformations A:V→V and A^∗:V→V that satisfy (i) and (ii) below:

(i)

There exists a basis for V with respect to which the matrix representing A is irreducible tridiagonal and the matrix representing A^∗ is diagonal.

(ii)

There exists a basis for V with respect to which the matrix representing A^∗ is irreducible tridiagonal and the matrix representing A is diagonal.

We call such a pair a Leonard pair on V. In this paper, we characterize the Leonard pairs using the notion of a tail. This notion is borrowed from algebraic graph theory.     

The minimum of the antichains in the factor poset

Denote g(m, n) the minimum of min A, where A is a subset of {1, 2, ..., m} of size n and there do not exist two distinct x and y in A such that x divides y. We use a method of poset to prove that g(m, n)=2 ⁱ for positive integer ilog₃ m and 1+s(m, i–1), where s(m, i) is the number of odd integers x such that m/3 ⁱ .Research was supported by National Science Council of Republic of China under Grant NSC74-0201-M008d-02.     

Lattices and infinite-dimensional forms. ‘The Lattice Method’

Hermitean vector spaces E of infinite dimensions are considered. Let G be a subgroup of the orthogonal group of E acting on a set M. The Lattice Method is a technique for classifying the orbits in M under G. We discuss the method in abstract terms and we illustrate it by means of three classification results showing that it is decisive to do a considerable amount of explicit calculations with vector subspace lattices.     

Multiple harmonic series related to multiple Euler numbers

In this paper, we define the multiple Euler numbers and consider some multiple harmonic series of Mordell-Tornheim's type, which is a partial sum of the Mordell-Tornheim zeta series defined by Matsumoto. Indeed, we prove a certain reducibility of these series as well as the multiple zeta values.     

Posets of copies of countable scattered linear orders

We show that the separative quotient of the poset 〈P(L),⊂〉$〈\mathbb{P}(L),\subset 〉$ of isomorphic suborders of a countable scattered linear order L is σ  -closed and atomless. So, under the CH, all these posets are forcing-equivalent (to (P(ω)/Fin)⁺${(P(\omega )/\mathrm{Fin})}^{+}$).     

On nilpotent subsemigroups of the matrix semigroup over an antiring

In this paper, nilpotent subsemigroups in the matrix semigroup over a commutative antiring are discussed. Some basic properties and characterizations for the nilpotent subsemigroups are given, and some equivalent conditions for the matrix semigroup over a commutative antiring to have a maximal nilpotent subsemigroup are obtained. Also, the maximal nilpotent subsemigroups in the matrix semigroup are described.     

The maximum dimension of a subspace of nilpotent matrices of index 2

A matrix M is nilpotent of index 2 if M²=0. Let V be a space of nilpotent n×n matrices of index 2 over a field k where and suppose that r is the maximum rank of any matrix in V. The object of this paper is to give an elementary proof of the fact that . We show that the inequality is sharp and construct all such subspaces of maximum dimension. We use the result to find the maximum dimension of spaces of anti-commuting matrices and zero subalgebras of special Jordan Algebras.     

Jordan structures of strictly lower triangular completions of nilpotent matrices

This work is part of a doctoral thesis, written under the supervision of Prof. A. Berman. It was supported by the Fund for Promotion of Research at the Technion.     

Multiple LU factorizations of a singular matrix

A singular matrix A may have more than one LU factorizations. In this work the set of all LU factorizations of A is explicitly described when the lower triangular matrix L is nonsingular. To this purpose, a canonical form of A under left multiplication by unit lower triangular matrices is introduced. This canonical form allows us to characterize the matrices that have an LU factorization and to parametrize all possible LU factorizations. Formulae in terms of quotient of minors of A are presented for the entries of this canonical form.