A note on commuting pairs of matrices

We give a short proof of the Motzkin-Taussky result that the variety of commuting pairs of matrices is irreducible. An easy consequence of this is that any two generated commutative subalgebra of n×n matrices has dimension at most n. We also answer an old question of Gerstenhaber by showing that the set of commuting triples of n×n matrices is not irreducible for n≥32.     

Linear Operators that Preserve Commuting Pairs of Nonnegative Real Matrices

A pair of n×n matrices (A, B) is called a commuting pair if AB=BA. We characterize the linear operators that preserve the set of commuting pairs of matrices over a subsemiring of nonnegative real numbers.     

Triangular stochastic matrices generated by infinitesimal elements

We show that each element in the semigroup S _n of all n × n non-singular upper (or lower) triangular stochastic matrices is generated by the infinitesimal elements of S _n, which form a cone consisting of all n × n upper (or lower) triangular intensity matrices.     

On approximately simultaneously diagonalizable matrices

A collection A₁, A₂, …, A_k of n × n matrices over the complex numbers C has the ASD property if the matrices can be perturbed by an arbitrarily small amount so that they become simultaneously diagonalizable. Such a collection must perforce be commuting. We show by a direct matrix proof that the ASD property holds for three commuting matrices when one of them is 2-regular (dimension of eigenspaces is at most 2). Corollaries include results of Gerstenhaber and Neubauer-Sethuraman on bounds for the dimension of the algebra generated by A₁, A₂, …, A_k. Even when the ASD property fails, our techniques can produce a good bound on the dimension of this subalgebra. For example, we establish for commuting matrices A₁, …, A_k when one of them is 2-regular. This bound is sharp. One offshoot of our work is the introduction of a new canonical form, the H-form, for matrices over an algebraically closed field. The H-form of a matrix is a sparse “Jordan like” upper triangular matrix which allows us to assume that any commuting matrices are also upper triangular. (The Jordan form itself does not accommodate this.)     

Involutions for upper triangular matrix algebras

In this paper we describe completely the involutions of the first kind of the algebra UT_n(F) of n×n upper triangular matrices. Every such involution can be extended uniquely to an involution on the full matrix algebra. We describe the equivalence classes of involutions on the upper triangular matrices. There are two distinct classes for UT_n(F) when n is even and a single class in the odd case.Furthermore we consider the algebra UT₂(F) of the 2×2 upper triangular matrices over an infinite field F of characteristic different from 2. For every involution *, we describe the *-polynomial identities for this algebra. We exhibit bases of the corresponding ideals of identities with involution, and compute the Hilbert (or Poincaré) series and the codimension sequences of the respective relatively free algebras.Then we consider the *-polynomial identities for the algebra UT₃(F) over a field of characteristic zero. We describe a finite generating set of the ideal of *-identities for this algebra. These generators are quite a few, and their degrees are relatively large. It seems to us that the problem of describing the *-identities for the algebra UT_n(F) of the n×n upper triangular matrices may be much more complicated than in the case of ordinary polynomial identities.     

Adjacency preserving bijective maps on triangular matrices over any division ring

Let 𝕋 _n (D) be the set of n × n upper triangular matrices over a division ring D. We characterize the adjacency preserving bijective maps in both directions on 𝕋 _n (D) (n ≥ 3). As applications, we describe the ring semi-automorphisms and the Jordan automorphisms on upper triangular matrices over a simple Artinian ring.     

Commutativity of the adjacency matrices of graphs

We say that two graphs G₁ and G₂ with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers n such that the complete bipartite graph K_n,n is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most n−1 linearly independent commuting adjacency matrices of size n; and if this bound occurs, then there exists a Hadamard matrix of order n. Finally, we determine the centralizers of some families of graphs.     

Maps preserving square-zero matrices on the algebra consisting of all upper triangular matrices

Let F be a field, T _n (F) (respectively, N _n (F)) the matrix algebra consisting of all n × n upper triangular matrices (respectively, strictly upper triangular matrices) over F. A ∈ T _n (F) is said to be square zero if A ² = 0. In this article, we firstly characterize non-singular linear maps on N _n (F) preserving square-zero matrices in both directions, then by using it we determine non-singular linear maps on T _n (F) preserving square-zero matrices in both directions.     

Iterative character constructions for algebra groups

We construct a family of orthogonal characters of an algebra group which decompose the supercharacters defined by Diaconis and Isaacs (2008) [6]. Like supercharacters, these characters are given by nonnegative integer linear combinations of Kirillov functions and are induced from linear supercharacters of certain algebra subgroups. We derive a formula for these characters and give a condition for their irreducibility; generalizing a theorem of Otto (2010) [20], we also show that each such character has the same number of Kirillov functions and irreducible characters as constituents. In proving these results, we observe as an application how a recent computation by Evseev (2010) [7] implies that every irreducible character of the unitriangular group UTn(q) of unipotent n×n upper triangular matrices over a finite field with q elements is a Kirillov function if and only if n?12. As a further application, we discuss some more general conditions showing that Kirillov functions are characters, and describe some results related to counting the irreducible constituents of supercharacters.     

Commuting decompositions of complete graphs

We say that two graphs G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph K is decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph K_n is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs     

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.     

On the variety of almost commuting nilpotent matrices

Let V be an n-dimensional vector space over an algebraically closed field and $\mathcal{N}Let V be an n-dimensional vector space over an algebraically closed field and N\mathcal{N} the nilcone of nilpotent endomorphisms of V. We study the variety A = {(X, Y, i, j) ? N ×N ×V ×V^* |[X, Y] = ij} \mathcal{A} = \left\{{(X, Y, i, j) \in \mathcal{N} \times \mathcal{N} \times V \times V^{\ast} \vert [X, Y] = ij}\right\} which is closely related to the variety of pairs of nilpotent n × n matrices with commutator of rank at most 1. We describe its irreducible components: two of them correspond to the pairs of commuting matrices, and n − 2 components of smaller dimension corresponding to the pairs of rank one commutator. In our proof we define a map to the zero fiber of the Hilbert scheme of points and study the image and the fibers.     

Commuting Graphs of Matrix Algebras

The commuting graph of a ring R, denoted by Γ(R), is a graph whose vertices are all noncentral elements of R, and two distinct vertices x and y are adjacent if and only if xy = yx. The commuting graph of a group G, denoted by Γ(G), is similarly defined. In this article we investigate some graph-theoretic properties of Γ(M _n (F)), where F is a field and n ≥ 2. Also we study the commuting graphs of some classical groups such as GL _n (F) and SL _n (F). We show that Γ(M _n (F)) is a connected graph if and only if every field extension of F of degree n contains a proper intermediate field. We prove that apart from finitely many fields, a similar result is true for Γ(GL _n (F)) and Γ(SL _n (F)). Also we show that for two fields F and E and integers n, m ≥ 2, if Γ(M _n (F))?Γ(M _m (E)), then n = m and |F|=|E|.     

Involutions in triangular groups

We describe involutions, i.e. elements of order 2, in the groups T _n (K) – of upper triangular matrices of dimension n (n?∈??), and T _∞(K) – of upper triangular infinite matrices, where K is a field of characteristic different from 2. Using the obtained result, we give a formula for the number of all involutions in T _n (K) in the case when K is a finite field.     

Restricted Isometry Property of Matrices with?Independent Columns and Neighborly Polytopes by?Random Sampling

This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors ±X ₁,…,±X _N ∈ℝ ⁿ , (N≥n). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries that satisfy uniformly a subexponential tail inequality possess the restricted isometry property with overwhelming probability. We show that such “sensing” matrices are valid for the exact reconstruction process of m-sparse vectors via ℓ ₁ minimization with m≤Cn/log ²(cN/n). The class of sampling matrices we study includes the case of matrices with columns that are independent isotropic vectors with log-concave densities. We deduce that if K⊂ℝ ⁿ is a convex body and X ₁,…,X _N ∈K are i.i.d. random vectors uniformly distributed on K, then, with overwhelming probability, the symmetric convex hull of these points is an m-centrally-neighborly polytope with m∼n/log ²(cN/n).     

Majors of Functions

We investigate the minor order of functions, focusing on upper covers and common upper bounds of pairs of functions. We show that two functions of arities m and n have a common upper bound if and only if they have a common lower bound, and if a common upper bound exists, then there is one of arity m + n ? 1. Moreover, we determine the possible essential arities of upper covers of functions.     

Determinantal varieties over truncated polynomial rings

We study components and dimensions of higher-order determinantal varieties obtained by considering generic m×n (m?n) matrices over rings of the form F[t]/(t^k), and for some fixed r, setting the coefficients of powers of t of all r×r minors to zero. These varieties can be interpreted as spaces of (k−1)th order jets over the classical determinantal varieties; a special case of these varieties first appeared in a problem in commuting matrices. We show that when r=m, the varieties are irreducible, but when r<m, these varieties are reducible. We show that when r=2<m (any k), there are exactly ⌊k/2⌋+1 components, which we determine explicitly, and for general r<m, we show there are at least ⌊k/2⌋+1 components. We also determine the components explicitly for k=2 and 3 for all values of r (for k=3 for all but finitely many pairs of (m,n)).     

Pairs of matrices that preserve the value of a generalized matrix function on the set of the upper triangular matrices

Let H be a subgroup of the symmetric group of degree m and let χ be an irreducible character of H. In this paper we give conditions that characterize the pairs of matrices that leave invariant the value of a generalized matrix function associated with H and χ, on the set of the upper triangular matrices.     

Random walk on upper triangular matrices mixes rapidly

We present an upper bound O(n ² ) for the mixing time of a simple random walk on upper triangular matrices. We show that this bound is sharp up to a constant, and find tight bounds on the eigenvalue gap. We conclude by applying our results to indicate that the asymmetric exclusion process on a circle indeed mixes more rapidly than the corresponding symmetric process. Received: 25 January 1999 / Revised version: 17 September 1999 / Published online: 14 June 2000