\input amstex
\input amsppt.sty

\nologo

\magnification1200
\hsize13cm
\vsize19cm

\def\al{\alpha}
\def\be{\beta}
\def\Om{\Omega}
\def\om{\omega}
\def\F{\Cal F}
\def\Mat{\operatorname{Mat}}
\def\const{\operatorname{const}}
\def\Span{\operatorname{span}}

\topmatter 
\title On a decomposition of square matrices over a ring with identity
\endtitle 
\author Heinz L\"uneburg
\endauthor 
\address 
Fachbereich Mathematik der Universit\"at Kaiserslautern,
Pfaffenbergstra\ss e 95, D-6750 Kaiserslautern
\endaddress

\endtopmatter
\document

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

\roster 
\item $P_{ij}\in\{0,1\}$ for all $i,j\in\{0,1,\dots,n-1\}$.
\item Each row of $P$ contains exactly one 1.
\item Each column of $P$ contains exactly one 1.
\endroster

Denote by $S_n$ the symmetric group on the set $\{0,1,\dots,n-1\}$. If
$\pi\in S_n$ then we define $P(\pi)$ by
$$P(\pi)_{ij}:=\cases 1&\text{if $\pi(j)=i$,} \\
0&\text{else.}\endcases $$
Then $P(\pi)$ 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\times 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(\pi):\pi\in 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.

\proclaim{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)\times(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:
\smallskip

{\rm(1)} $V_1$ consists of all $a\in\Mat_{n+1}(R)$ such that
$a_{ni}=a_{in}=0$ for $0\le i\le n-1$ and $a_{nn}=\sum _{j=0}
^{n-1}a_{n-1,j}$. 
\smallskip

{\rm(2)} Let $a$ be an $n$- and $b$ be an $(n-1)$-tuple over
$R$. Define the matrices $C(a)$ and $D(b)$ by
$$\pmatrix
 0&a_n&\dots &a_3&a_2&a_1\\
a_1&0&a_n&\dots &a_3&a_2\\
a_2&a_1&0&a_n&\dots &a_3\\
\vdots&&\ddots&\ddots&\ddots&\vdots \\
a_{n-1}&\dots&a_2&a_1&0&a_n\\
a_n&\dots &a_3&a_2&a_1&0&
\endpmatrix$$
and
$$\pmatrix
X&0&0&\dots &0&0\\
0&0&b_{n-1}&\dots &b_2&b_1\\
0&b_1&0&b_{n-1}&\dots &b_2\\
\vdots&&\ddots&\ddots&\ddots&\vdots \\
0&\dots&b_2&b_1&0&b_{n-1}\\
0&b_{n-1}&\dots &b_2&b_1&0&
\endpmatrix$$
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)$.

{\rm(3)} $V_3$ is the set of all $a\in\Mat_{n+1}(R)$ with $a_{ij}=0$ for
all $(i,j)$ different from $(n,0)$ and $(n,n)$.
\smallskip

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)$.
\endproclaim

The proof is left as an exercise to the reader.

\proclaim{Theorem 2}Same assumptions and notations as in
Theorem~{\rm1}. Define the permutations $\al,\be\in S_{n+1}$ by
$\al:=(0,1,2,\dots,n)$ and $\be:=(1,2,\dots,n)$ and set
$B(i):=P(\al^i)$ for $i=1,2,\dots,n$ and $B(n+i):=P(\be ^i)$ for
$i=1,2,\dots,n-1$. Then $\{B(i):1\le i\le 2n-1\}$  is a basis for $V_2$.
\endproclaim
\demo{Proof}Straightforward.
\enddemo

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

\proclaim{Theorem 3}Denote by $\const_{n+1}(R)$ the set of all
$a\in\Mat_{n+1}(R)$ such that there exists an $r\in R$ with $\sum
_{k=0} ^{n}a_{kj}=r=\sum _{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.
\endproclaim

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)$.
$$\align & \quad (0)\quad /\quad (0,1)\quad /\quad (0,1,2),\ (0,2,1),\
(1,2)\quad /\quad 
(0,1,2,3),\ (0,2)(1,3),\\
& (0,3,2,1),\ (1,2,3),\ (1,3,2), \quad /\quad (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).
\endalign$$
$$
\matrix 
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
\endmatrix\qquad 
\matrix 
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
\endmatrix\qquad 
\matrix 
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
\endmatrix\qquad 
\matrix 
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
\endmatrix\hphantom{.}
$$
\medskip
$$
\matrix 
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
\endmatrix\qquad
\matrix
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
\endmatrix\qquad
\matrix
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\\
\endmatrix\qquad
\matrix
 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
\endmatrix.
$$


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.






\enddocument
