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_{ij} = \delta_{i+1,j}, \quad L_{ij} = \delta_{i,j+1},$

where $\delta_{ij}$ is the Kronecker delta symbol.

For example, the 5 × 5 shift matrices are

: $U_5 = \begin{pmatrix}
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{pmatrix} \quad
L_5 = \begin{pmatrix}
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{pmatrix}.$

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.{{harvtxt|Beauregard|Fraleigh|1973|p=312}}

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ⁿ = 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:

{{unordered list

| 1=L^T = U; U^T = L

| 2=The null spaces of U and L are

: $N(U) = \operatorname{span}\left\{ (1, 0, \ldots, 0)^\mathsf{T} \right\},$

: $N(L) = \operatorname{span}\left\{ (0, \ldots, 0, 1)^\mathsf{T} \right\}.$

| 3=The spectrum of U and L is $\{0\}$ . The algebraic multiplicity of 0 is n, and its geometric multiplicity is 1. From the expressions for the null spaces, it follows that (up to a scaling) the only eigenvector for U is $(1, 0, \ldots, 0)^\mathsf{T}$ , and the only eigenvector for L is $(0, \ldots, 0, 1)^\mathsf{T}$ .

| 4=For LU and UL we have

: $UL = I - \operatorname{diag}(0, \ldots, 0, 1),$

: $LU = I - \operatorname{diag}(1, 0, \ldots, 0).$

These matrices are both idempotent, symmetric, and have the same rank as U and L

| 5=L^n−aU^n−a + L^aU^a = U^n−aL^n−a + U^aL^a = I (the identity matrix), for any integer a between 0 and n inclusive.

}}

If N is any nilpotent matrix, then N is similar to a block diagonal matrix of the form

: $\begin{pmatrix}
S_1 & 0 & \ldots & 0 \\
0 & S_2 & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & S_r
\end{pmatrix}$

where each of the blocks S₁, S₂, ..., S_r is a shift matrix (possibly of different sizes).{{harvtxt|Beauregard|Fraleigh|1973|pp=312,313}}{{harvtxt|Herstein|1964|p=250}}

Examples

: $S = \begin{pmatrix}
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{pmatrix}; \quad A = \begin{pmatrix}
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{pmatrix}.$

Then,

: $SA = \begin{pmatrix}
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{pmatrix}; \quad AS = \begin{pmatrix}
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{pmatrix}.$

Clearly there are many possible permutations. For example, $S^\mathsf{T} A S$ is equal to the matrix A shifted up and left along the main diagonal.

: $S^\mathsf{T}AS=\begin{pmatrix}
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{pmatrix}.$

Notes

References

{{citation | first1 = Raymond A. | last1 = Beauregard | first2 = John B. | last2 = Fraleigh | year = 1973 | isbn = 0-395-14017-X | title = A First Course In Linear Algebra: with Optional Introduction to Groups, Rings, and Fields | publisher = Houghton Mifflin | location = Boston | url-access = registration | url = https://archive.org/details/firstcourseinlin0000beau |oclc=1019797576}}
{{ citation | first1 = I. N. | last1 = Herstein | year = 1964 | isbn = 978-1-114-54101-6 | title = Topics In Algebra | publisher = Blaisdell Publishing | location = Waltham |oclc=1419919702 |url=https://openlibrary.org/books/OL5885700M}}

External links

[http://www.ee.imperial.ac.uk/hp/staff/dmb/matrix/special.html#Shift_Matrix Shift Matrix - entry in the Matrix Reference Manual]

Category:Matrices (mathematics)

Category:Sparse matrices