Shuffle Algorithm for Descriptor Systems

The so-called shuffle algorithm suggested by Luenberger [1] can be used to check the regularity of a matrix pencil $sE-A$ and to compute its index $\mathrm{ind}(E,A)$. The algorithm starts with $i:=0$, $E_{i}:=$, and $A_{i}:=A$. While $E$ is singular perform the following operation:

  1. Perform a row reduction on $E_{i}$ using a matrix $R_{i}$ with \[ R_{i}E_{i}=\begin{pmatrix} \overline{E}_{i}\\ \\0 \end{pmatrix},\quad R_{i}A_{i}=\begin{pmatrix} \overline{A}_{i}\\ \\ \tilde{A}_{i} \end{pmatrix} \] such that $E_{i}$ is row regular.
  2. Then, set \[ E_{i+1}:=\left(\begin{array}{c} \overline{E}_{i}\\ \\ \tilde{A}_{i} \end{array}\right),\quad A_{i+1}:=\left(\begin{array}{c} \overline{A}_{i}\\ \\0 \end{array}\right),\quad i:=i+1. \]

If this procedure terminates, the matrix pencil is regular and has $\mathrm{ind}(E,A)=i$, see [2]. In Scilab, the shuffle algorithm can be implemented using the function $\mathtt{rowshuff}$.

Example

The shuffle algorithm will be demonstrated using the matrices \[ E=\left(\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{array}\right)\quad\mbox{and}\quad A=\left(\begin{array}{ccc} 0 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{array}\right). \]

We start with $i=0$, $E_{0}=E$ and $A_{0}=A$. The matrix~$E_{0}$ is singular ($\mathrm{rank}E_{0}=2$). Since $E_{0}$ is already in row reduced form, we can use $R_{0}=I$ to get \[ E_{1}=\left(\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 0 & 1 \end{array}\right),\quad A_{1}=\left(\begin{array}{ccc} 0 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0 \end{array}\right),\quad i=1. \] Again, $E_{1}$ is singular. With \[ R_{1}=\left(\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & -1 \end{array}\right) \] we get \[ R_{1}E_{1}=\left(\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{array}\right),\quad R_{1}A_{1}=\left(\begin{array}{ccc} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 1 & 0 \end{array}\right). \] This yields the matrices \[ E_{2}=\left(\begin{array}{ccc} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{array}\right)\quad\mbox{and}\quad A_{2}=\left(\begin{array}{ccc} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{array}\right). \] The resulting matrix $E_{2}$ is regular. Hence, the pencil is regular with $\mathrm{ind}(E,A)=2$.

References:

  1. Luenberger, D. G.: Time-Invariant Descriptor Systems. Automatica, 1978, 14, 473-480
  2. Griepentrog, E. & März, R.: Basic Proberties of Some Differential-Algebraic Equations. Zeitschrift für Analysis und ihre Anwendung, 1989, 8, 25-40