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.     

Two generators for the general linear groups over finite fields

For every finite field F and every n≥2, the group GL(n,F) can be generated by two elements (which are explicitly described). The multiplicative semigroup of all n by n matrices over F can then be generated by three elements.     

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.     

Local trace forms

Let F be a local field of characteristic ≠2 and K a Galois extension field of F of degree n. Then K can be viewed as a quadratic space over F under the bilinear form T(xy)=tr_K/Fxy for xyεK. The invariants of this form are given in the case when n is odd; when n is even and F is nondyadic; and when n is evesF dyadic, and K/F is unramifed.     

Similarity over SL(n, F)

Let F be a finite field. It is shown that if AB axe n × n matrices with entries from F which are similar over GL(n, F), then AB are similar over SL(n, F), provided that some elementary divisor of xl- A is irreducible over F. The result remains true if F is any field such that any element of F may be represented as the norm of an element of any finite algebraic extension of F.     

Large spaces of symmetric matrices of bounded rank are decomposable

Let k and n be positive integers such that k≤n. Let S_n(F) denote the space of all n×n symmetric matrices over the field F with char F≠2. A subspace L of S_n(F) is said to be a k-subspace if rank A≤k for every AεL.

Now suppose that k is even, and write k=2r. We say a k∥-subspace of S_n(F) is decomposable if there exists in Fⁿ a subspace W of dimension n-r such that x^tAx=0 for every xεWAεL.

We show here, under some mild assumptions on kn and F, that every k∥-subspace of S_n(F) of sufficiently large dimension must be decomposable. This is an analogue of a result obtained by Atkinson and Lloyd for corresponding subspaces of F^m,n.     

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).     

Linear mappings which are rank-k nonincreasing, II

We prove the following result. Let F be an infinite field of characteristic other than two. Let k be a positive integer. Let S_n(F) denote the space of all n × n symmetric matrices with entries in F, and let T:S_n(F)→S_n(F) be a linear operator. Suppose that T is rank-k nonincreasing and its image contains a matrix with rank higher than K. Then, there exist λεF and PεF^n,n such that T(A)=λPAP^t for all AεS_n(F). λ can be chosen to be 1 if F is algebraically closed and ±1 if F=R, the real field.     

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.     

Sums and products of matrices with prescribed similarity classes

Let F be a field and let A and n × n matrices over F. We study some properties of A^' + B^' and A^'B^', when A^' and B^' run over the sets of the matrices similar to A and B, respectively.     

Diagonal flips in pseudo-triangulations on closed surfaces

Negami has already shown that there is a natural number N(F²) for any closed surface F² such that two triangulations on F² with n vertices can be transformed into each other by a sequence of diagonal flips if nN(F²). We investigate the same theorem for pseudo-triangulations with or without loops, estimating the length of a sequence of diagonal flips. Our arguments will be applied to simple triangulations to obtain a linear upper bound for N(F²) with respect to the genus of F².     

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).     

The identity as a matrix commutator

If A is an n×n matrix over a field F of positive characteristic p, then I_n=AB-BA, for some matrix B, iff p divides the size of each Jordan block of A.     

The minimal polynomial of a matrix

Let Rbe a finite dimensional central simple algebra over a field FA be any n× n matrix over R. By using the method of matrix representation, this paper obtains the structure formula of the minimal polynomial q_A(λ) of A over F. By using q_A(λ), this paper discusses the structure of right (left) eigenvalues set of A, and obtains the necessary and sufficient condition that a matrix over a finite dimensional central division algebra is similar to a diagonal matrix.     

The rank of the difference of matrices with prescribed similarity classes

Let F be a field and let A,B be n × n matrices over I. We study the rank of A' - B' when A and B run over the set of matrices similar to A and B, respectively.     

Quadratic expansions of spectral functions

A function, F, on the space of n×n real symmetric matrices is called spectral if it depends only on the eigenvalues of its argument, that is F(A)=F(UAU^T) for every orthogonal U and symmetric A in its domain. Spectral functions are in one-to-one correspondence with the symmetric functions on : those that are invariant under arbitrary swapping of their arguments. In this paper we show that a spectral function has a quadratic expansion around a point A if and only if its corresponding symmetric function has quadratic expansion around λ(A) (the vector of eigenvalues). We also give a concise and easy to use formula for the ‘Hessian' of the spectral function. In the case of convex functions we show that a positive definite ‘Hessian' of f implies positive definiteness of the ‘Hessian' of F.     

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.     

ContributionsChromatic Ramsey numbers

Suppose G is a graph. The chromatic Ramsey number r_c(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let M_n = min[r_c(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that M_n = (n − 1)² + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M₆ and M₇.     

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.     

Explicit formulas for the Dumont-Foata polynomial

Dumont and Foata have defined a polynomial F_n(x, y, z) recursively. They proved that F_n(x, y, z) is symmetric in x, y, z and that F_n(1, 1, 1) = G_2n+2 the Genocchi number. Moreover, they gave an elegant combinatorial interpretation for the coefficients of F_n(x, y, z). In the present paper explicit formulas and generating functions for F_n(x, y, z) are obtained.