Criteria for the stability of the finiteness property and for the uniqueness of Barabanov norms

A set of matrices is said to have the finiteness property if the maximal rate of exponential growth of long products of matrices drawn from that set is realised by a periodic product. The extent to which the finiteness property is prevalent among finite sets of matrices is the subject of ongoing research. In this article, we give a condition on a finite irreducible set of matrices which guarantees that the finiteness property holds not only for that set, but also for all sufficiently nearby sets of equal cardinality. We also prove a theorem giving conditions under which the Barabanov norm associated to a finite irreducible set of matrices is unique up to multiplication by a scalar, and show that in certain cases these conditions are also persistent under small perturbations.     

On the finiteness property for rational matrices

We analyze the periodicity of optimal long products of matrices. A set of matrices is said to have the finiteness property if the maximal rate of growth of long products of matrices taken from the set can be obtained by a periodic product. It was conjectured a decade ago that all finite sets of real matrices have the finiteness property. This “finiteness conjecture” is now known to be false but no explicit counterexample is available and in particular it is unclear if a counterexample is possible whose matrices have rational or binary entries. In this paper, we prove that all finite sets of nonnegative rational matrices have the finiteness property if and only if pairs of binary matrices do and we state a similar result when negative entries are allowed. We also show that all pairs of 2×2 binary matrices have the finiteness property. These results have direct implications for the stability problem for sets of matrices. Stability is algorithmically decidable for sets of matrices that have the finiteness property and so it follows from our results that if all pairs of binary matrices have the finiteness property then stability is decidable for nonnegative rational matrices. This would be in sharp contrast with the fact that the related problem of boundedness is known to be undecidable for sets of nonnegative rational matrices.     

Triangular Matrix Representations

In this paper we develop the theory of generalized triangular matrix representation in an abstract setting. This is accomplished by introducing the concept of a set of left triangulating idempotents. These idempotents determine a generalized triangular matrix representation for an algebra. The existence of a set of left triangulating idempotents does not depend on any specific conditions on the algebras; however, if the algebra satisfies a mild finiteness condition, then such a set can be refined to a “complete” set of left triangulating idempotents in which each “diagonal” subalgebra has no nontrivial generalized triangular matrix representation. We then apply our theory to obtain new results on generalized triangular matrix representations, including extensions of several well known results.     

On Some Generalized Polyhedral Convex Constructions

Generalized polyhedral convex sets, generalized polyhedral convex functions on locally convex Hausdorff topological vector spaces, and the related constructions such as sum of sets, sum of functions, directional derivative, infimal convolution, normal cone, conjugate function, subdifferential are studied thoroughly in this paper. Among other things, we show how a generalized polyhedral convex set can be characterized through the finiteness of the number of its faces. In addition, it is proved that the infimal convolution of a generalized polyhedral convex function and a polyhedral convex function is a polyhedral convex function. The obtained results can be applied to scalar optimization problems described by generalized polyhedral convex sets and generalized polyhedral convex functions.     

The Finite and the Infinite

In ZF set theory finiteness classes are introduced and their stability under basic set theoretical constructions are being investigated. Typical results are:

Finiteness property of pairs of 2×2 sign-matrices via real extremal polytope norms

This paper deals with the joint spectral radius of a finite set of matrices. We say that a set of matrices has the finiteness property if the maximal rate of growth, in the multiplicative semigroup it generates, is given by the powers of a finite product.Here we address the problem of establishing the finiteness property of pairs of $2\times 2$ sign-matrices. Such problem is related to the conjecture that pairs of sign-matrices fulfil the finiteness property for any dimension. This would imply, by a recent result by Blondel and Jungers, that finite sets of rational matrices fulfil the finiteness property, which would be very important in terms of the computation of the joint spectral radius. The technique used in this paper could suggest an extension of the analysis to $n\times n$ sign-matrices, which still remains an open problem.As a main tool of our proof we make use of a procedure to find a so-called real extremal polytope norm for the set. In particular, we present an algorithm which, under some suitable assumptions, is able to check if a certain product in the multiplicative semigroup is spectrum maximizing.For pairs of sign-matrices we develop the computations exactly and hence are able to prove analytically the finiteness property. On the other hand, the algorithm can be used in a floating point arithmetic and provide a general tool for approximating the joint spectral radius of a set of matrices.     

A geometric approach to forbidden minors for GF(3)

A new proof is given based on known results about embeddings of geometric lattices in projective spaces, of the finiteness of the set of forbidden minors for matroid representation over GF(3). This approach is more abstract than previous ones in that it does not depend on explicitly producing the minors in question, and for this reason it is hoped that further progress can be made along these lines on the question of finiteness of the set of forbidden minors for arbitrary GF(q).     

On permutation polytopes

In this paper we lay the foundations for the study of permutation polytopes: the convex hull of a group of permutation matrices.We clarify the relevant notions of equivalence, prove a product theorem, and discuss centrally symmetric permutation polytopes. We provide a number of combinatorial properties of (faces of) permutation polytopes. As an application, we classify ?4-dimensional permutation polytopes and the corresponding permutation groups. Classification results and further examples are made available online.We conclude with several questions suggested by a general finiteness result.     

Existential monadic second order logic on random rooted trees

We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton–Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).     

Endomorphisms of abelian varieties and points of finite order in characteristic p

An analog of the Tate hypothesis on homomorphisms of Abelian varieties is proved, in which points of sufficiently large prime order figure in place of the Tate modules. As is the case with the Tate hypothesis, this assertion follows formally from a finiteness hypothesis for isogenies of Abelian varieties, which is proved in characteristic p > 2 and for finite fields. The same methods are used to prove the finiteness of the set of Abelian varieties of a given dimension over a finite field.Translated from Matematicheskie Zametki, Vol. 21, No. 6, pp. 737–744, June, 1977.     

Shunkov Groups Saturated by General Linear Groups of Degree 3

Siberian Mathematical Journal - Saturation and the related concept of a saturating set are among the finiteness conditions for infinite groups. Saturation is applied to studying periodic...     

Finiteness Theorems for Graphs and Posets Obtained by Compositions

We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it.In particular we show that the following classes have infinite antichains with respect to the induced subgraph/poset relation: interval graphs and orders, N-free orders, orders with bounded decomposition width. On the other hand for orders with bounded decomposition diameter finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties.     

Über projektive Moduln und Endlichkeitshindernisse bei Transformationsgruppen

We study projective modules in the category of functors from homogeneous spaces into abelian groups. Such functors have been considered by Bredon [1]. We show that protective functors are determined by a set of ordinary projective modules over suitable group rings. The general notions are applied to give a quick proof for the product formula of the finiteness obstruction for transformation groups. These finiteness obstructions are straightforward extensions of the Swan-Wall obstructions (see e. g. Quinn [7]). They are important in the study of homotopy representations (tom Dieck — Petrie [3], [4]). This work is also related to Rothenberg [8].     

The Complexity of 2-Fold Branched Coverings of a 3-Sphere

Complexity is a function which maps a set of 3-manifolds to a set of nonnegative integers. This function has some natural properties (finiteness, additivity, etc.) and it shows, in some sense how complex the manifold is. This function seems important for the classification of 3-manifolds. We evaluate of the complexity of 2-fold branched coverings of a 3-sphere. We present a theoretical estimate and compare it with experimental data.     

Finiteness conditions and distributive laws for Boolean algebras

We compare diverse degrees of compactness and finiteness in Boolean algebras with each other and investigate the influence of weak choice principles. Our arguments rely on a discussion of infinitary distributive laws and generalized prime elements in Boolean algebras. In ZF set theory without choice, a Boolean algebra is Dedekind finite if and only if it satisfies the ascending chain condition. The Denumerable Subset Axiom (DS) implies finiteness of Boolean algebras with compact top, whereas the converse fails in ZF. Moreover, we derive from DS the atomicity of continuous Boolean algebras. Some of the results extend to more general structures like pseudocomplemented semilattices (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

高数教学中的有限与无限问题

为了纠正学生在高等数学中因对无限问题认识不足而容易出现的错误,从集合、极限及求和方面阐述了数学中的有限问题与无限问题。     

On the arithmetic of Krull monoids with infinite cyclic class group

Let H be a Krull monoid with infinite cyclic class group G and let G_P⊂G denote the set of classes containing prime divisors. We study under which conditions on G_P some of the main finiteness properties of factorization theory-such as local tameness, the finiteness and rationality of the elasticity, the structure theorem for sets of lengths, the finiteness of the catenary degree, and the existence of monotone and near monotone chains of factorizations-hold in H. In many cases, we derive explicit characterizations.     

Tensor Complementarity Problems with Finite Solution Sets

Journal of Optimization Theory and Applications - In this paper, we first extend the concept of non-degenerate matrices to tensors and we then study the finiteness properties of the solution set of...