next up previous
Next: 4. Splitting criteria Up: Splitting algorithm for vector Previous: 2. Block type Bruhat

3. Row-minimal matrices


(3.1) In virtue of Lemma 2 we shall look for presentation matrices which have a good chance of being equivalent to a matrix in block diagonal form.

Definition 3  
For a given $ J \subset \{ 1,...,r \} $ we call Q a J-row-minimal matrix if $
{\cal M}(P_{\sigma} Q) $ is minimal in the set of Rk-submodules $ \{ {\cal M}(UP_{\sigma} Q) \mid U \in {I\!\!B}_+ \} $, where $ P_{\sigma} $ is a permutation matrix such that the associated permutation $ \sigma $ maps J to J0.

Obviously, this notation is independent of the choice of $ \sigma $. Moreover, Q is called row-minimal if it is J-row-minimal with respect to all strict subsets J of row indices $ \{ 1,...,r \} $.


(3.2) The test for whether a module M will split is based on the observation that a presentation matrix of M in block diagonal form Q0 is J0- and J'0-row-minimal (cf. Lemma 2). It is possible to check by a standard basis computation whether a row-minimal matrix Q is equivalent to a block diagonal matrix. To do that, we have to fix an arbitrary (local) monomial order of Rr, ordering first by components; that is, $ m \underline{e}_i > m' \underline{e}_j $ for any two monomials $ m,\ m' $ and $ i<j, \ \underline{e}_i $ the i-th unit column.


(3.3) Let $ Q' \sim Q $ be a matrix formed by an ordered standard basis of $\langle Q\rangle$. From the above order we obtain an integer l such that all columns of Q' having index l'> l will have their first non-zero entry in the k'-th component, k'>k. Hence Q' will have the block structure

\begin{displaymath}Q' = \left( \begin{array}{rr}
A' & 0 \\
C' & D' \end{array}
\right) , \quad A' \in \mbox{Mat}\, (k,l;R),

and the modules associated to A' and D' are characterized by Q:

\begin{displaymath}\langle A' \rangle = {\cal M}(Q), \quad \langle D' \rangle =
\end{array} \right)
\in \langle Q \rangle

Changing the roles of J0 and J'0 (resp. reversing the order of components) we may write a corresponding standard basis Q'' in analogous block form

\begin{displaymath}Q'' = \left( \begin{array}{cr}
A'' & B'' \\
0 & D'' \end{array}

Comparing these two different standard bases of Q, we obtain as a trivial consequence

Lemma 4  
With the notation from above

\begin{displaymath}Q \sim Q_0 \quad \mbox{if and only if} \quad \langle A'\rangl...
...\quad \mbox{and} \quad \langle D'\rangle = \langle D''\rangle.


(3.4) Usually we are not in this situation and we first have to apply row operations. But, assuming J0-row-minimality, it is enough to apply only those row-operations belonging to $I\!\!B_+$:

Proposition 5  
  If $ Q' \sim UQ_0 $ for some $ U \in {\,I\!\!\!\!G} $ and
if Q' is J0-row-minimal, then
(i1) $ \langle A'\rangle = {\cal M}(Q) \cong {\cal M}(Q_0) = \langle A\rangle $
(i2) $ {\underline{0} \choose \underline{y}} \in \langle Q \rangle
\Longleftrightarrow \underline{y} \in {\cal M}' (Q_0)$; that is, $\langle D'\rangle
= \langle D \rangle $.

(i0) First note that given an isomorphism $ \varphi :R^l \rightarrow R^l $ and a $ \varphi^{-1} $-invariant submodule $ N \subset R^l $, then N is $ \varphi $-invariant, too (otherwise $ N \subset \varphi (N) \subset \varphi ^2 (N) \ldots$ would produce an infinite ascending chain!).
(i1) With the notation of (3.3) let

\begin{displaymath}Q \sim Q' =
\left( \begin{array}{rc}
A' & 0 \\
C' & D' \e...
...eft( \begin{array}{rl}
A & 0 \\
0 & D \end{array} \right).

Letting $ \tilde A := SA, \tilde D := WD$, $\tilde I := I+VT $, we obtain

\begin{displaymath}\left( \begin{array}{cc}
A' & 0 \\
C' & D'
\end{array} \...
... \\
V \tilde A & \tilde I \tilde D
\end {array}
\right), \end{displaymath}

$ {\cal M}(Q) = \langle A'\rangle = \langle \tilde A \rangle + \langle T \tilde D \rangle \supseteq
\langle \tilde A \rangle \cong \langle A \rangle $. Because of the minimality assumption,

\begin{displaymath}\langle \tilde A \rangle \subseteq {\cal M}(Q) \subseteq {\ca...
...- \tilde T \\
0 & I \end{array}
\right) \cdot Q

Again, by Lemma 1(i3), we have a factorization

\begin{displaymath}\left( \begin{array}{rr}
I & 0 \\
V & I \end{array}
\tilde S & 0 \\
0 & \tilde W \end{array} \right).

Consequently, we obtain

\begin{displaymath}{\cal M}\left( \left( \begin{array}{rc}
I & - \tilde T \\
\langle \tilde S \tilde A \rangle,

and, by the initial remark, $ \langle \tilde A \rangle = {\cal M}(Q) = \langle \tilde S
\tilde A \rangle $.
(i2) An easy computation shows that

\begin{eqnarray*}\underline{y} \in \langle D' \rangle
& \Longleftrightarrow
...{y} = V \tilde A \underline f + \tilde I \tilde D \underline g . \end{eqnarray*}

Thus, $ \underline{y} = (\tilde I - VT) \tilde D g = (I + VT - VT) \tilde D \underline g =
\tilde D g $, which shows that $ \langle D'\rangle \subseteq \langle \tilde D \rangle $. On the other hand $ \underline{y} \in
\langle \tilde D \rangle $ implies the existence of a $ \underline{g} $ such that $ \underline{y} = \tilde D \underline{g}$. Because $ \langle T \tilde D \rangle
\subseteq \langle A' \rangle = \langle A \rangle $, there is an $\underline{f}$ such that $\ -T \tilde Dg = \tilde A \underline{f}$; that is, $\left( \begin{array}{r}
\underline{0} \\ \underline{y}
\end{array} \right)
\in \langle Q \rangle $ and $ \underline{y} \in \langle D' \rangle $.
next up previous
Next: 4. Splitting criteria Up: Splitting algorithm for vector Previous: 2. Block type Bruhat
| ZCA Home | Reports |