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'' × ''n'' shift matrix ''S'' becomes the zero 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'' × ''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
* tr(''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^\mathsf A S$ 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 (mathematics)
Sparse matrices