Matchings in simplicial complexes, circuits and toric varieties

Using a generalized notion of matching in a simplicial complex and circuits of vector configurations, we compute lower bounds for the minimum number of generators, the binomial arithmetical rank and the A-homogeneous arithmetical rank of a lattice ideal. Prime lattice ideals are toric ideals, i.e. the defining ideals of toric varieties.     

Binomial arithmetical rank of lattice ideals

 In this paper, we will show that a lattice ideal is a complete intersection if and only if its binomial arithmetical rank equals its height, if the characteristic of the base field k is zero. And we will give the condition that a binomial ideal equals a lattice ideal up to radical in the case of char k=0. Further, we will study the upper bound of the binomial arithmetical rank of lattice ideals and give a sharp bound for the lattice ideals of codimension two. Received: 12 June 2001 / Revised version: 22 July 2002     

A condition for modular lattices

This paper proves that a geometric lattice of rank n is a modular lattice if its every maximal chain contains a modular element of rank greater than 1 and less than n. This result is generalized to a more general lattices of finite rank. The first author is partially supported by the National Natural Science Foundation of China (Grant No. 10471016).     

Idempotent Block Splitting on Partial Partitions,I: Isotone Operators

Image segmentation algorithms can be modelled as image-guided operators (maps) on the complete lattice of partitions of space, or on the one of partial partitions (i.e., partitions of subsets of the space). In particular region-splitting segmentation algorithms correspond to block splitting operators on the lattice of partial partitions, in other words anti-extensive operators that act by splitting each block independently. This first paper studies in detail block splitting operators and their lattice-theoretical and monoid properties; in particular we consider their idempotence (a requirement in image segmentation). We characterize block splitting openings (kernel operators) as operators splitting each block into its connected components according to a partial connection; furthermore, block splitting openings constitute a complete sublattice of the complete lattice of all openings on partial partitions. Our results underlie the connective approach to image segmentation introduced by Serra. The second paper will study two classes of non-isotone idempotent block splitting operators, that are also relevant to image segmentation.     

The Number of Lattice Rules of Specified Upper Class and Rank

The upper class of a lattice rule is a convenient entity for classification and other purposes. The rank of a lattice rule is a basic characteristic, also used for classification. By introducing a rank proportionality factor and obtaining certain recurrence relations, we show how many lattice rules of each rank exist in any prime upper class. The Sylow p-decomposition may be used to obtain corresponding results for any upper class.     

Determination of the rank of an integration lattice

The continuing and widespread use of lattice rules for high-dimensional numerical quadrature is driving the development of a rich and detailed theory. Part of this theory is devoted to computer searches for rules, appropriate to particular situations. In some applications, one is interested in obtaining the (lattice) rank of a lattice rule Q(Λ) directly from the elements of a generator matrix B (possibly in upper triangular lattice form) of the corresponding dual lattice Λ^⊥. We treat this problem in detail, demonstrating the connections between this (lattice) rank and the conventional matrix rank deficiency of modulo p versions of B. AMS subject classification (2000) 65D30     

Further ways to approximate the exponential of a matrix

A product formula is established, and applied to approximate exp(A) in terms of the exponentials of the components of a splitting,or additive decomposition, of A. In the cases considered, these latter exponentials are given by explicit formulae. Thus, the exponentials of L, D, U in the splitting A= L + D + U are easily computed, since L and U are nilpotent and D is diagonal. A formula for the exponential of a rank one matrix is given, and may be used in conjunction with any one of a number of expressions of A as a sum of matrices of rank one. A priori estimates of the relative errors in the approximations thus obtained are supplied. The methods described were suggested by, and are extensions of the "splitting" methods described by C. Moler and C. Van Loan [SIAM Review 20 (1978), p. 826].     

Finite distributive lattices and the splitting property

We show that a finite distributive lattice has the splitting property - every maximal antichain splits into two parts so that the lattice is the union of the upset of one part and the downset of the other - if and only if it is a Boolean lattice or is one of three other lattices. We also introduce a measure of "how splitting" a finite distributive lattice is, and investigate it. Received June 13, 2001; accepted in final form July 1, 2002.     

Estimates of the number of relative minima of lattices

We prove an estimate of the number of relative minima of an arbitrary lattice (which can be noninteger and incomplete) located in a given cube. This estimate is correct up to a constant depending on the dimension and rank.     

On well-rounded sublattices of the hexagonal lattice

We produce an explicit parameterization of well-rounded sublattices of the hexagonal lattice in the plane, splitting them into similarity classes. We use this parameterization to study the number, the greatest minimal norm, and the highest signal-to-noise ratio of well-rounded sublattices of the hexagonal lattice of a fixed index. This investigation parallels earlier work by Bernstein, Sloane, and Wright where similar questions were addressed on the space of all sublattices of the hexagonal lattice. Our restriction is motivated by the importance of well-rounded lattices for discrete optimization problems. Finally, we also discuss the existence of a natural combinatorial structure on the set of similarity classes of well-rounded sublattices of the hexagonal lattice, induced by the action of a certain matrix monoid.     

Linear Inequalities for Rank 3 Geometric Lattices

The flag Whitney numbers (also referred to as the flag f-numbers) of a geometric lattice count the number of chains of the lattice with elements having specified ranks. We give a collection of inequalities which imply all the linear inequalities satisfied by the flag Whitney numbers of rank 3 geometric lattices. We further describe the smallest closed convex set containing the flag Whitney numbers of rank 3 geometric lattices as well as the smallest closed convex set containing the flag Whitney numbers of those lattices corresponding to oriented matroids.     

Smooth lattices over quadratic integers

We construct lattices with quadratic structure over the integers in quadratic number fields having the property that the rank of the quadratic structure is constant and equal to the rank of the lattice in all reductions modulo maximal ideals. We characterize the case in which such lattices are free. The construction gives a representative of the genus of such lattices as an orthogonal sum of “standard” pieces of ranks 1–4 and covers the case of the discriminant of the real quadratic number field congruent to 1 modulo 8 for which a general construction was not known.      

A counterexample to the generalization of Sperner's theorem

It has been conjectured that the analog of Sperner's theorem on non-comparable subsets of a set holds for arbitrary geometric lattices, namely, that the maximal number of non-comparable elements in a finite geometric lattice is max w(k), where w(k) is the number of elements of rank k. It is shown in this note that the conjecture is not true in general. A class of geometric lattices, each of which is a bond lattice of a finite graph, is constructed in which the conjecture fails to hold.     

Face numbers of Engström representations of matroids

A classic problem in the theory of matroids is to find a subspace arrangement, such as a hyperplane or pseudosphere arrangement, whose intersection poset is isomorphic to a prescribed geometric lattice. Engström gave an explicit construction for an infinite family of such arrangements, indexed by the set of finite regular CW complexes. In this paper, we compute the face numbers of these topological representations in terms of the face numbers of the indexing complexes and give upper bounds on the total number of faces in these objects. Moreover, for a fixed rank, we show that the total number of faces in the Engström representation corresponding to a codimension one homotopy sphere arrangement is bounded above by a polynomial in the number of elements of the matroid, whose degree is one less than the matroid’s rank.     

On some maximal non-selfadjoint operator algebras

We show that the reflexive algebra given by the lattice generated by a maximal nest and a rank one projection is maximal with respect to its diagonal.     

A nonconvex approach to low‐rank matrix completion using convex optimization

This paper deals with the problem of recovering an unknown low‐rank matrix from a sampling of its entries. For its solution, we consider a nonconvex approach based on the minimization of a nonconvex functional that is the sum of a convex fidelity term and a nonconvex, nonsmooth relaxation of the rank function. We show that by a suitable choice of this nonconvex penalty, it is possible, under mild assumptions, to use also in this matrix setting the iterative forward–backward splitting method. Specifically, we propose the use of certain parameter dependent nonconvex penalties that with a good choice of the parameter value allow us to solve in the backward step a convex minimization problem, and we exploit this result to prove the convergence of the iterative forward–backward splitting algorithm. Based on the theoretical results, we develop for the solution of the matrix completion problem the efficient iterative improved matrix completion forward–backward algorithm, which exhibits lower computing times and improved recovery performance when compared with the best state‐of‐the‐art algorithms for matrix completion. Copyright © 2016 John Wiley & Sons, Ltd.     

A Constructive Approach to Lattice Rule Canonical Forms

The rank and invariants of a general lattice rule are conventionally defined in terms of the group-theoretic properties of the rule. Here we give a constructive definition of the rank and invariants using integer matrices. This underpins a nonabstract algorithm set in matrix algebra for obtaining the Sylow p-decomposition of a lattice rule. This approach is particularly useful when it is not known whether the form in which the lattice rule is specified is canonical or even repetitive. A new set of necessary and sufficient conditions for recognizing a canonical form is given.     

The decomposition of idempotents associated with inflators

In a recent paper, Friedland, Hershkowitz, and Schneider introduced a new matrix product called the inflation product and a new class of matrices called inflators. Fundamental to the constructions were certain idempotent matrices associated with the inflators. This paper studies the structure of the idempotent matrix associated with an inflator. In particular, it is shown that if the idempotent associated with an inflator has rank greater than one, then the idempotent can be split into several pairwise orthogonal idempotents of lower rank such that the resultant idempotents are associated with inflators which are inflation product factors of the original inflator. The indecomposable idempotents associated with the decomposition of an inflator are characterized in terms of rank, and are shown to be generally nonunique. The number of indecomposable idempotents in a splitting is shown to be invariant.