Reducibility of matrix polynomials and their traces

Résumé Pour des variables matriciellesn x n, nous démontrons la réductibilité en degré de certains produits et de leurs traces, afin de généraliser au delà des dimensions 2 ou 3 quelques résultats employés parRivlin, Smith etSpencer, pour extraire une base d'intégrité orthogonale des tenseurs symétriques. En particulier, pourn3, nous démontrons la réductibilité en degré de tout produit de 2 ⁿ –1 matrices et de la trace de tel produit.

---

---

The work described in this paper was carried out under Contract No. 562 (40).     

Determinant of the distance matrix of a tree with matrix weights

Let T be a tree with n vertices and let D be the distance matrix of T. According to a classical result due to Graham and Pollack, the determinant of D is a function of n, but does not depend on T. We allow the edges of T to carry weights, which are square matrices of a fixed order. The distance matrix D of T is then defined in a natural way. We obtain a formula for the determinant of D, which involves only the determinants of the sum and the product of the weight matrices.     

Reducibility number

Let P be a poset in a class of posets P. A smallest positive integer r is called reducibility number of P with respect to P if there exists a non-empty subset S of P with |S|=r and P-S∈P. The reducibility numbers for the power set 2ⁿ of an n-set (n?2) with respect to the classes of distributive lattices, modular lattices and Boolean lattices are calculated. Also, it is shown that the reducibility number r of the lattice of all subgroups of a finite group G with respect to the class of all distributive lattices is 1 if and only if the order of G has at most two distinct prime divisors; further if r is a prime number then order of G is divisible by exactly three distinct primes. The class of pseudo-complemented u-posets is shown to be reducible. Deletable elements in semidistributive posets are characterized.     

Reducibility on families

A reducibility on families of subsets of natural numbers is introduced which allows the family per se to be treated without its representation by natural numbers being fixed. This reducibility is used to study a series of problems both in classical computability and on admissible sets: for example, describing index sets of families belonging to , generalizing Friedberg’s completeness theorem for a suitable reducibility on admissible sets, etc. *Supported by RFBR (project No. 05-01-00605) and by the Council for Grants (under RF President) and State Aid of Young Candidates of Science (grant MK-4314.2008.1). **Supported by RFBR (projects No. 08-01-00442 and 06-04002-DFGa), by the Council for Grants (under RF President) of Leading Scientific Schools (grant NSh-335.2008.1), and by the Russian Foundation for Support of Domestic Science. Translated from Algebra i Logika, Vol. 48, No. 1, pp. 31-53, January-February, 2009.     

Flow Hypergraph Reducibility

Reducible flow graphs were first defined by Hecht and Ullman in terms of intervals; another definition, based on two flow graph transformations, was also presented. In this paper, we extend the notion of reducibility to directed hypergraphs, proving that the interval and the transformation approaches are still equivalent when applied to this family.     

Reducibility of hyperplane arrangements

Certain problems on reducibility of central hyperplane arrangements are settled. Firstly, a necessary and sufficient condition on reducibility is obtained. More precisely, it is proved that the number of irreducible components of a central hyperplane arrangement equals the dimension of the space consisting of the logarithmic derivations of the arrangement with degree zero or one. Secondly, it is proved that the decomposition of an arrangement into a direct sum of its irreducible components is unique up to an isomorphism of the ambient space. Thirdly, an effective algorithm for determining the number of irreducible components and decomposing an arrangement into a direct sum of its irreducible components is offered. This algorithm can decide whether an arrangement is reducible, and if it is the case, what the defining equations of irreducible components are.     

Reducibility of pointlike problems

We show that the pointlike and the idempotent pointlike problems are reducible with respect to natural signatures in the following cases: the pseudovariety of all finite semigroups in which the order of every subgroup is a product of elements of a fixed set \(\pi \) of primes; the pseudovariety of all finite semigroups in which every regular \(\mathcal J\)-class is the product of a rectangular band by a group from a fixed pseudovariety of groups that is reducible for the pointlike problem, respectively graph reducible. Allowing only trivial groups, we obtain \(\omega \)-reducibility of the pointlike and idempotent pointlike problems, respectively for the pseudovarieties of all finite aperiodic semigroups (\(\mathsf{A}\)) and of all finite semigroups in which all regular elements are idempotents (\(\mathsf{DA}\)).     

Homogeneous weights of matrix product codes over finite principal ideal rings

In this paper, the homogeneous weights of matrix product codes over finite principal ideal rings are studied and a lower bound for the minimum homogeneous weights of such matrix product codes is obtained.     

Perturbations of strongly continuous operator semigroups,and matrix Muckenhoupt weights

Let A and A ₀ be linear continuously invertible operators on a Hilbert space ? such that A ^?1 ? A ₀ ^?1 has finite rank. Assuming that σ(A ₀) = ? and that the operator semigroup V ₊(t) = exp{iA ₀ t}, t ≥ 0, is of class C ₀, we state criteria under which the semigroups U _±(t) = exp{±iAt}, t ≥ 0, are of class C ₀ as well. The analysis in the paper is based on functional models for nonself-adjoint operators and techniques of matrix Muckenhoupt weights.     

Reducibility of finite reflection groups

A finite (pseudo-)reflection group G naturally gives rise to a hyperplane arrangement,i.e.,its reflection arrangement.We show that G is reducible if and only if its reflection arrangement is reducible.     

Reducibility of covers of AFT shifts

In this paper we show that the reducibility structure of several covers of sofic shifts is a flow invariant. In addition, we prove that for an irreducible subshift of almost finite type the left Krieger cover and the past set cover are reducible. We provide an example which shows that there are non almost finite type shifts which have reducible left Krieger covers. As an application we show that the Matsumoto algebra of an irreducible, strictly sofic shift of almost finite type is not simple.     

Wadge Reducibility and Infinite Computations

This is a survey of results about Wadge reducibility in some spaces and its relation to the study of infinite (non-terminating) computations. We also discuss the related techniques and directions of future research. Supported by DFG-RFBR Grant 06-01-04002 and by RFBR grant 07-01-00543a.     

交换矩阵半群的可约性

首先分别给出单生矩阵半群或者摹群不可约、不可分解以及完全可约的充分必要条件,其次讨论一般域上矩阵半群的可约性的一些条件,最后特别地讨论实数域上矩阵半群的可约性,完全确定了实数域上对称和反对称矩阵组成的不可约交换矩阵半群.     

A distance-metric methodology for the derivation of weights from a pairwise comparison matrix

A variety of approaches exist for the determination of a weighting scheme from a pairwise comparison matrix describing a scale-relation between objectives or alternatives. The most common context for such an algorithm is that of the analytic hierarchy process (AHP), although uses in other areas of the field of multicriteria decision making (MCDM) can also be found. Typically, the eigenvalue method is the standard method employed in the AHP to determine weights, as in the ExpertChoice software. However, another class of techniques are the distance-metric-based approaches, which are frequently proposed as alternatives to the eigenvalue method. This paper evaluates such distance-metric-based approaches comparing their effectiveness, using the eigenvalue method as a benchmark. A common framework is introduced to establish an efficient frontier for method comparison.     

Reducibility of translates of Dickson polynomials

Let be a field and . The Dickson polynomial is characterized by the equation . We prove that is reducible if and only if there is a prime such that for some , or and for some . This result generalizes the well-known reducibility criterion for binomials; and it provides a reducibility criterion for where denotes the Chebyshev polynomial of degree .