ON A DECOMPOSITION OF SQUARE

MATRICES OVER A RING WITH IDENTITY

Heinz Lüneburg

Let R be a not necessarily commutative ring with 1 and let P be an (n×n)-matrix over R. Then P is called a permutation matrix if, and only if, the following conditions are satisfied:

(1) P_{ij} ∈ {0, 1} for all i, j ∈ {0, 1, …, n − 1}.

(2) Each row of P contains exactly one 1.

(3) Each column of P contains exactly one 1.

Denote by S_{n} the symmetric group on the set {0, 1, …, n − 1}. If π ∈ S_{n} then we define P (π) by

P (π)_{ij} := \{ \begin{matrix}1 & if π(j) = i, \\ 0 & else. \end{matrix}

Then P (π) is a permutation matrix and all permutations matrices are obtained in this way, as is well-known.

The set Mat_{n}(K) of all (n × n)-matrices over the field K forms a vector space of dimension n^{2} over K and it belongs to the folklore of permutation matrices that

dim(span({P (π) : π ∈ S_{n}})) = (n − 1)^{2} + 1.

Linear Algebra tells us that there exists a basis of the span of permutation matrices consisting entirely of permutation matrices. Searching for such a basis yields a much more general theorem.

Theorem 1. Let R be a not necessarily commutative ring with 1 and let n by a positive integer. Consider the set Mat_{n+1}(R) of all ((n + 1) × (n + 1))-matrices over R as a left R-module. Define the submodules V_{1}, V_{2}, V_{3} of Mat_{n+1}(R) as follows:

(1) V_{1} consists of all a ∈ Mat_{n+1}(R) such that a_{ni} = a_{in} = 0 for 0 ≤ i ≤ n − 1 and a_{nn} = ∑_{j=0}^{n−1} a_{n−1,j}.

(2) Let a be an n- and b be an (n − 1)-tuple over R. Define the matrices C(a) and D(b) by

( \begin{matrix}0 & a_{n} & … & a_{3} & a_{2} & a_{1} \\ a_{1} & 0 & a_{n} & … & a_{3} & a_{2} \\ a_{2} & a_{1} & 0 & a_{n} & … & a_{3} \\ ⋮ & & ... & ... & ... & ⋮ \\ a_{n−1} & … & a_{2} & a_{1} & 0 & a_{n} \\ a_{n} & … & a_{3} & a_{2} & a_{1} & 0 \end{matrix} )

and

( \begin{matrix}X & 0 & 0 & … & 0 & 0 \\ 0 & 0 & b_{n−1} & … & b_{2} & b_{1} \\ 0 & b_{1} & 0 & b_{n−1} & … & b_{2} \\ ⋮ & & ... & ... & ... & ⋮ \\ 0 & … & b_{2} & b_{1} & 0 & b_{n−1} \\ 0 & b_{n−1} & … & b_{2} & b_{1} & 0 \end{matrix} )

respectively, where X is the sum of the b_{i}’s. Then V_{2} consists of all matrices of the form C(a) + D(b).

(3) V_{3} is the set of all a ∈ Mat_{n+1}(R) with a_{ij} = 0 for all (i, j) different from (n, 0) and (n, n).

Then Mat_{n+1}(R) is the direct sum of V_{1}, V_{2}, V_{3}. Moreover, V_{1} is, as an R-module, isomorphic to Mat_{n}(R).

The proof is left as an exercise to the reader.

Theorem 2. Same assumptions and notations as in Theorem 1. Define the permutations α, β ∈ S_{n+1} by α := (0, 1, 2, …, n) and β := (1, 2, …, n) and set B(i) := P (α^{i}) for i = 1, 2, …, n and B(n + i) := P (β^{i}) for i = 1, 2, …, n − 1. Then {B(i) : 1 ≤ i ≤ 2n − 1} is a basis for V_{2}.

Proof. Straightforward.

As a consequence of Theorems 1 and 2 we get the following theorem.

Theorem 3. Denote by const_{n+1}(R) the set of all a ∈ Mat_{n+1}(R) such that there exists an r ∈ R with ∑_{k=0}^{n} a_{kj} = r = ∑_{l=0}^{n} a_{il} for all i and j. Then const_{n+1}(R) is a direct summand of Mat_{n+1}(R) having a basis consisting of n^{2} + 1 permutation matrices.

Theorems 1 and 2 give a recursion for a basis of const_{n+1}(R) as well as for a basis of a complement of const_{n+1}(R). As an example, we list the 17 permutations whose permutation matrices form a basis of const_{5}(R). The /’s indicate the steps in the recursion. Moreover, we list a set of 8 matrices forming a basis of a complement of const_{5}(R).

(0) / (0, 1) / (0, 1, 2), (0, 2, 1), (1, 2) / (0, 1, 2, 3), (0, 2)(1, 3),
(0, 3, 2, 1), (1, 2, 3), (1, 3, 2), / (0, 1, 2, 3, 4), (0, 2, 4, 1, 3), (0, 3, 1, 4, 2),
(0, 4, 3, 2, 1), (1, 2, 3, 4), (1, 3)(2, 4), (1, 4, 3, 2).

0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1  0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1  0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1  0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 .

The recursion for the basis of const_{n+1}(R) clearly shows that const_{n+1}(R) has a basis consisting of n^{2} + 1 permutation matrices.

Fachbereich Mathematik der Universität Kaiserslautern, Pfaffenbergstraße 95, D-6750 Kaiserslautern