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 row vector one position to the right, with a zero appearing in the first position. An upper shift matrix shifts the components of a row vector one position to the left, with a zero appearing in the last position.[1]

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 shift matrices are nilpotent; an n by n shift matrix S becomes the null matrix when raised to the power of its dimension n.

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:

p_U(\lambda) = (-1)^n\lambda^n.

The following properties show how U and L are related:

 N(U) = \operatorname{span}\{ (1,0,\ldots, 0)^T \},
 N(L) = \operatorname{span}\{ (0,\ldots, 0, 1)^T \}.
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

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 S1, S2, ..., Sr is a shift matrix (possibly of different sizes).[2][3]

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^{T}AS is equal to the matrix A shifted up and left along the main diagonal.


S^{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}.

See also

Notes

  1. Beauregard & Fraleigh (1973, p. 312)
  2. Beauregard & Fraleigh (1973, pp. 312,313)
  3. Herstein (1964, p. 250)

References

External links

This article is issued from Wikipedia - version of the Wednesday, March 23, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.