Matrices with zero trace as commutators of nilpotents

Let C ∈ F^n×n have minimum polynomial m(x). Suppose C is of zero trace and m(x) splits over F. Then, except when n = 2 and m(x) = (x - c)² or when n = 3 and m(x) = x - c)² with c ≠ 0, there exist nilpotents A, B ∈ F^n×n such that C = AB - BA.     

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.     

The countability index of the endomorphism semigroup of a vector space

The countability index C(S) of a semigroup S is the least positive integer n, if such an integer exists, with the property that every countable subset of S is contained in a subsemigroup with n generators. If no such integer exists. C(S) is defined to be infinite. Let V be a vector space over a field F and denote by End V the endomorphism semigroup of V. In the two main results, it is determined precisely when C(End V)=2 and when C(End V)=x SpecificallyC(End V)=2 if and only if V is infinite dimensional or dim V=1 and F is finite and C(End V)=x if and only if F is infinite and dim V is an integer N≥1.     

Linear transformations on symmetric matrices II

Let Tbe a linear mapping on the space of n× nsymmetric matrices over a field Fof characteristic not equal to two. We obtain the structure of Tfor the following cases:(i) Tpreserves matrices of rank less than three; (ii) Tpreserves nonzero matrices of rank less than K + 1 where Kis a fixed positive integer less than nand Fis algebraically closed; (iii) Tpreserves rank Kmatrices where Kis a fixed odd integer and Fis algebraically closed.     

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.     

Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs:

(1) P_n, a path on n vertices;

(2) K_1,n^s, the graph obtained from K_1,n by subdividing an edge once;

(3) K_2,ne, the graph obtained from K_2,n by deleting an edge;

(4) K_2,n⁺, the graph obtained from K_2,n by adding an edge between the two degree-n vertices x₁ and x₂, and a pendent edge at each x_i.

Two applications of this result are also discussed in the paper.     

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.     

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.     

Pascal k-elminated functional matrix and eulerian numbers

In this paper we shall first introduce the Pascal k-eliminated functional matrices P_n,k[xyz] and CP_n,k[xyz]. Then, using these matrices we obtain several important combinatorial identities. Finally, using the matrix inversion of P_n,k[xyz] and CP_n,k[xyz], we derive an interesting formula for Eulerian numbers [7]     

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.     

Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

Trace forms of normal extensions over local fields

Let k be a local field of char(k)≠2 and K/k a finite field extension of degree n. Then K can be viewed as a quadratic space of k under the quadratic form T(X) =tr_K/k(x²). The invariants of this form are given in the case when K/k is a Galois extension, except for Galois extensions K/k with k dyadicn divisible by 4 and the 2-Sylowgroups of the Galois group are non-cyclic. Conversely all quadratic forms of a local field k of char(k)≠ 2 which appear as trace forms of Galois extensions of k are determined.     

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.     

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

Valuations defined by Ostrowski nets

Ostrowski proved that if v is a valuation on an algebraically closed field F and if w is a valuation extending v to the field F (x) of rational functions over F, then w is defined by a transcendental pseudo-convergent net (that is, an Ostrowski net) or w is a Rella extension of v centered about x − c for some c in F. In this paper, valuations on the field of rational functions over an arbitrary field determined by Ostrowski nets, along with the topologies they generate, are investigated.     

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.     

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.     

Vectors with a prescribed minimal polynomial

Let V be a finite dimensional vector space over the field Fand φ (x)∈F[x].LetxV → V be a linear operator. Let S_φbe the set consisting of the vectors whose minimal polynomial φ(x)together with the zero vector We give necessary and sufficieni condition for S _φ to be a subspace.     

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.     

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.