Shift matrix

{{short description|Square matrix with ones on a superdiagonal or subdiagonal}} 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 :<math>U_{ij} = \delta_{i+1,j}, \quad L_{ij} = \delta_{i,j+1},</math>

where <math>\delta_{ij}</math> is the Kronecker delta symbol.

For example, the 5 × 5 shift matrices are :<math>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}.</math>

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

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 *: <math>p_U(\lambda) = (-1)^n\lambda^n.</math> * ''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: {{unordered list | 1=''L''T = ''U''; ''U''T = L | 2=The null spaces of ''U'' and ''L'' are : <math>N(U) = \operatorname{span}\left\{ (1, 0, \ldots, 0)^\mathsf{T} \right\},</math> : <math>N(L) = \operatorname{span}\left\{ (0, \ldots, 0, 1)^\mathsf{T} \right\}.</math> | 3=The spectrum of ''U'' and ''L'' is <math>\{0\}</math>. 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 <math>(1, 0, \ldots, 0)^\mathsf{T}</math>, and the only eigenvector for ''L'' is <math>(0, \ldots, 0, 1)^\mathsf{T}</math>. | 4=For ''LU'' and ''UL'' we have : <math>UL = I - \operatorname{diag}(0, \ldots, 0, 1),</math> : <math>LU = I - \operatorname{diag}(1, 0, \ldots, 0).</math>

These matrices are both idempotent, symmetric, and have the same rank as ''U'' and ''L'' | 5=''L''''n''−''a''''U''''n''−''a'' + ''L''''a''''U''''a'' = ''U''''n''−''a''''L''''n''−''a'' + ''U''''a''''L''''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 : <math>\begin{pmatrix} S_1 & 0 & \ldots & 0 \\ 0 & S_2 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & S_r \end{pmatrix}</math>

where each of the blocks ''S''1, ''S''2, ..., ''S''''r'' is a shift matrix (possibly of different sizes).<ref>{{harvtxt|Beauregard|Fraleigh|1973|pp=312,313}}</ref><ref>{{harvtxt|Herstein|1964|p=250}}</ref>

==Examples==

: <math>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}.</math>

Then, : <math>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}.</math>

Clearly there are many possible permutations. For example, <math>S^\mathsf{T} A S</math> is equal to the matrix ''A'' shifted up and left along the main diagonal. : <math> 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}.</math>

==Notes== <references/>

==References== {{refbegin}} * {{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 | ol = 5885700M |oclc=1419919702 |url=https://openlibrary.org/books/OL5885700M}} {{refend}}

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