Shift Matrix

In mathematics, a shift matrix is a binary matrix with ones only on the superdiagonal or subdiagonal, and zeroes elsewhere. A shift matrix ''U'' with ones on the superdiagonal is an upper shift matrix. The alternative subdiagonal matrix ''L'' is unsurprisingly known as a lower shift matrix. The (''i'',''j''):th component of ''U'' and ''L'' are
:$U_ = \delta_, \quad L_ = \delta_,$

where $\delta_$ is the Kronecker delta symbol.

For example, the ''5×5'' shift matrices are
:$U_5 = \begin 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 \end \quad L_5 = \begin 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 \end.$

Clearly, the transpose of a lower shift matrix is an upper shift matrix and vice versa.

As a linear transformation, a lower shift matrix shifts the components of a column vector one position down, with a zero appearing in the first position. An upper shift matrix shifts the components of a column vector one position up, with a zero appearing in the last position.

Premultiplying a matrix ''A'' by a lower shift matrix results in the elements of ''A'' being shifted downward by one position, with zeroes appearing in the top row. Postmultiplication by a lower shift matrix results in a shift left.
Similar operations involving an upper shift matrix result in the opposite shift.

Clearly all finite-dimensional shift matrices are nilpotent; an ''n'' by ''n'' shift matrix ''S'' becomes the null matrix when raised to the power of its dimension ''n''.

Shift matrices act on shift spaces. The infinite-dimensional shift matrices are particularly important for the study of ergodic systems. Important examples of infinite-dimensional shifts are the Bernoulli shift, which acts as a shift on Cantor space, and the Gauss map, which acts as a shift on the space of continued fractions (that is, on Baire space.)

Properties

Let ''L'' and ''U'' be the ''n'' by ''n'' lower and upper shift matrices, respectively. The following properties hold for both ''U'' and ''L''.
Let us therefore only list the properties for ''U'':
* det(''U'') = 0
* trace(''U'') = 0
* rank(''U'') = ''n'' − 1
* The characteristic polynomials of ''U'' is
*: $p_U(\lambda) = (-1)^n\lambda^n.$
* ''U''^''n'' = 0. This follows from the previous property by the Cayley–Hamilton theorem.
* The permanent of ''U'' is ''0''.

The following properties show how ''U'' and ''L'' are related:

If ''N'' is any nilpotent matrix, then ''N'' is similar to a block diagonal matrix of the form
:$\begin S_1 & 0 & \ldots & 0 \\ 0 & S_2 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & S_r \end$

where each of the blocks ''S''₁, ''S''₂, ..., ''S''_''r'' is a shift matrix (possibly of different sizes).

Examples

: $S=\begin 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 \end; \quad A = \begin 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 & 1 \\ 1 & 2 & 3 & 2 & 1 \\ 1 & 2 & 2 & 2 & 1 \\ 1 & 1 & 1 & 1 & 1 \end.$

Then,
: $SA = \begin 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 & 1 \\ 1 & 2 & 3 & 2 & 1 \\ 1 & 2 & 2 & 2 & 1 \end; \quad AS = \begin 1 & 1 & 1 & 1 & 0 \\ 2 & 2 & 2 & 1 & 0 \\ 2 & 3 & 2 & 1 & 0 \\ 2 & 2 & 2 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end.$

Clearly there are many possible permutations. For example, $S^\mathsfAS$ is equal to the matrix ''A'' shifted up and left along the main diagonal.
: $S^\mathsfAS=\begin 2 & 2 & 2 & 1 & 0 \\ 2 & 3 & 2 & 1 & 0 \\ 2 & 2 & 2 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end.$

See also

* Clock and shift matrices
* Nilpotent matrix
* Subshift of finite type

Notes

References

*
*

External links

Shift Matrix - entry in the Matrix Reference Manual

{{Matrix classes

Matrices
Sparse matrices