The construction of irreducible normalized representations of the general linear group

A method is described for constructing in an explicit form an irreducible representation T of M_n(F), the set of all n × n matrices over the real or complex field F, satisfying the condition T(A^*)=T^*(A) for all A∈M_n(F).     

Products of complic cosquares and pseudo-involutory matrices

LetF be a field with (nontrivial) involution (i.e.F-conjugation). A nonsingular matrix Aover Fis called a complic F-cosquare provided A=S^*-1for some matrix Sover Fand is called p.i. (pseudo-involutory) provided A=A^-1 It is shown that Ais a complic F-cosquare iff Ais the product of two p.i. matrices over Fand that det (AA)=1 iff Ais the product of two complic F-cosquares (hence iff A is the product of four p.i. matrices over F). It is conjectured that, except for one obvious case (2 x 2 matrices over the field of order 2), every unimodular matrix A over an arbitrary field Fis a product S¹ST:1T with S1 and Tover FThis conjecture is proved for matricesAof order ≤3.     

The maximun of i(XAX-1+B)

Let F be an algebraically closed field. We denote by i(A) the number of invariant polynomials of a square matrix A, which are different from 1. For A,B any n×n matrices over F, we calculate the maximum of i(XAX^-1+B), where X runs over the set of all non-singular n×n matrices over F.     

Commuting pairs and triples of matrices and related varieties

In this note, we show that the set of all commuting d-tuples of commuting n×n matrices that are contained in an n-dimensional commutative algebra is a closed set, and therefore, Gerstenhaber's theorem on commuting pairs of matrices is a consequence of the irreduciblity of the variety of commuting pairs. We show that the variety of commuting triples of 4×4 matrices is irreducible. We also study the variety of n-dimensional commutative subalgebras of M_n(F), and show that it is irreducible of dimension n²−n for n4, but reducible, of dimension greater than n²−n for n7.     

Equality of higher numerical ranges of matrices and a conjecture of Kippenhahn on Hermitian pencils

Let M_n be the algebra of all n × n complex matrices. For 1 k n, the kth numerical range of A M_n is defined by W_k(A) = (1/k)∑_j^k=1x_j^*Ax_j : x₁, …, x_k is an orthonormal set in ⁿ]. It is known that tr A/n = W_n(A) W_n−1(A) W₁(A). We study the condition on A under which W_m(A) = W_k(A) for some given 1 m < k n. It turns out that this study is closely related to a conjecture of Kippenhahn on Hermitian pencils. A new class of counterexamples to the conjecture is constructed, based on the theory of the numerical range.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

Limiting values of the variance and the moments of the dimension of a sum or intersection of random vector subspaces

Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U₁, …, U_m) of vector subspaces of W be uniformly distributed; and consider the statistics X_m,1 dim_F(∑_i=1^m U_i) and X_m,2 dim_F (∩_i=1^m U_i). If F is finite of cardinality q, we determine lim E(X_m,1^k), and lim E(X_m,2^k), and hence, lim var(X_m,1) and lim var(X_m,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F.     

Tree groups and the 4-string pure braid group

Given a graph Г, undirected, with no loops or multiple edges, we define the graph group on Г, F_Г, as the group generated by the vertices of Г, with one relation xy = xy for each pair x and y of adjacent vertices of Г.

In this paper we will show that the unpermuted braid group on four strings is an HNN-extension of the graph group F_s, where

S =

Full-size image

The form of the extension will resolve a conjecture of Tits for the 4-string braid group. We will conclude, by analyzing the subgroup structure of graph groups in the case of trees, that for any tree T on a countable vertex set, F_t is a subgroup of the 4-string braid group.

We will also show that this uncountable collection of subgroups of the 4-string braid group is linear, that is, each subgroup embeds in GL(3, ), as well as embedding in Aut(F), where F is the free group of rank 2.     

Some algebraic constructions in rational homotopy theory

In this note we describe constructions in the category of differential graded commutative algebras over the rational numbers Q which are analogs of the space F(X, Y) of continuous maps of X to Y, the component F(X, Y,ƒ) containing ƒ ε F(X, Y), fibrations, induced fibrations, the space Γ(π) of sections of a fibration π: E → X, and the component Γ(π,σ) containing σ ε Γ (π). As a focus, we address the problem of expressing π^*(F(X, Y, ƒ)) = Hom(π_*(F(X,Y, ƒ)),Q) in terms of differential graded algebra models for X and Y.     

On an explicit formula for the distribution of the supremum

Let M_∞ be the supremum of a random walk drifting to -∞ which is generated by the partial sums of a sequence of independent identically distributed random variables with a common distribution F. We prove that the moment generating function E exp(sM_∞) is a rational function if and only if the function ∫₀^∞ exp(sx)F(dx) is rational.     

A characterization on n-critical economical generalized tic-tac-toe games

There is a so called generalized tic-tac-toe game playing on a finite set X with winning sets A₁, A₂,…, A_m. Two players, F and S, take in turn a previous untaken vertex of X, with F going first. The one who takes all the vertices of some winning set first wins the game. Erd s and Selfridge proved that if |A₁|=|A₂|==|A_m|=n and m<2ⁿ⁻¹, then the game is a draw. This result is best possible in the sense that once m=2ⁿ⁻¹, then there is a family A₁, A₂,…, A_m so that F can win. In this paper we characterize all those sets A₁,…, A_2n−1 so that F can win in exactly n moves. We also get similar result in the biased games.     

Instabilities of robot motion

Instabilities of robot motion are caused by topological reasons. In this paper we find a relation between the topological properties of a configuration space (the structure of its cohomology algebra) and the character of instabilities, which are unavoidable in any motion planning algorithm. More specifically, let X denote the space of all admissible configurations of a mechanical system. A motion planner is given by a splitting X×X=F₁F₂F_k (where F₁,…,F_k are pairwise disjoint ENRs, see below) and by continuous maps s_j :F_j→PX, such that Es_j=1_Fj. Here PX denotes the space of all continuous paths in X (admissible motions of the system) and E :PX→X×X denotes the map which assigns to a path the pair of its initial–end points. Any motion planner determines an algorithm of motion planning for the system. In this paper we apply methods of algebraic topology to study the minimal number of sets F_j in any motion planner in X. We also introduce a new notion of order of instability of a motion planner; it describes the number of essentially distinct motions which may occur as a result of small perturbations of the input data. We find the minimal order of instability, which may have motion planners on a given configuration space X. We study a number of specific problems: motion of a rigid body in R³, a robot arm, motion in R³ in the presence of obstacles, and others.     

Additive Maps Preserving Moore-Penrose Inverses of Matrices on Symmetric Matrix Spaces

Suppose F is a field of characteristic not 2. Let M_nF and S_nF be the n × n full matrix space and symmetric matrix space over F, respectively. All additive maps from S_nF to S_nF (respectively, M_nF) preserving Moore-Penrose inverses of matrices are characterized. We first characterize all additive Moore-Penrose inverse preserving maps from S_nF to M_nF, and thereby, all additive Moore-Penrose inverse preserving maps from S_nF to itself are characterized by restricting the range of these additive maps into the symmetric matrix space.     

The cocharacter sequence of the finite dimensional grassmann algebra

Let V_k be a k-dimensional vector space and let E(V_k) be the finite dimensional Grass-mann algebra over a field F. We compute the sequence of cocharacters of the nilpotent algebra E^*(V_k) = E(V_k) - F.     

Compatibilité entre structures d''intervalles et relations d''orde

Compatibility between interval structures and partial orderings.

If H=(X,E) is a hypergraph, n the cardinality of X,I_n the ordered set {1..n} and < an order relation on X, we call F(X,<) the set of the one-to-one functions from X to I_n which are compatible with <. If AI_n we denote by (A) the length of the smallest interval of I_n which contains A.

We first deal with the following problem: Find ƒF(X,<) which minimise . The a_e, eR are positive coefficients.

This problem can be understood as a scheduling problem and is checked to be NP-complete. We learn how to recognize in polynomial time those hypergraphs H=(X,E) which induce an optimal value of z min equal to .

Next we work on a dual question which arises about interval graphs, when some partial orderings on the vertex set of these graphs intend to represent inclusion, overlapping or anteriority relations between closed intervals of the real line.     

A matrix problem associated with computing Cohen-Macaulay type

Suppose A∈M_n×m(F), B∈M_n×t(F) for some field F. Define Г(AB) to be the set of n×n diagonal matrices D such that the column space of DA is contained in the column space of B. In this paper we determine dim Г(AB). For matrices AB of the same rank we provide an algorithm for computing dim Г(AB).     

On the Equation n_1n_2= n_3n_4 Restricted to Factor Closed Sets

We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.     

Products of involutory matrices. I

It is shown that, for every integer ≥1 and every field F, each n×n matrix over F of determinant ±1 is the product of four involutory matrices over F. Products of three ×n involutory matrices over F are characterized for the special cases where n≤4 or F has prime order ≤5. It is also shown for every field F that every matrix over F of determinant ±1 having no more than two nontrivial invariant factors is a product of three involutory matrices over F.     

Comparison of two norms of matrices

Any complex n × n matrix A satisfies the inequality

A ₁ ≤ n 1/2 A _d

where .₁ is the trace norm and ._d is the norm defined by

Full-size image

,

where B is the set of orthonormal bases in the space of n × 1 matrices. The present work is devoted to the study of matrices A satisfying the identity:

A₁ = n1/2 A _d

This paper is a first step towards a characterization of matrices satisfying this identity. Actually, a workable characterization of matrices subject to this condition is obtained only for n = 2. For n = 3, a partial result on nilpotent matrices is presented. Like our previous study (J. Dazord, Linear Algebra Appl. 254 (1997) 67), this study is a continuation of the work of M. Marcus and M. Sandy (M. Marcus and M. Sandy, Linear and Multilinear Algebra 29 (1991) 283). Also this study is related to the work of R. Gabriel on classification of matrices with respect to unitary similarity (see R. Gabriel, J. Riene Angew, Math. 307/308 (1979) 31; R. Gabriel, Math. Z. 200 (1989) 591).