next up previous
Next: 6. Finding a J-row-reduction Up: Splitting algorithm for vector Previous: 4. Splitting criteria

5. Criteria for row-minimality


(5.1) Fix $ J= J_0 =\{ 1,...,k \}.$ Consider all those matrices $ U_T= \left( \begin{array}{rr}
I & T \\
0 & I \end{array} \right)
$ from $I\!\!B_+$ which do not increase $ {\cal M}(Q), \ Q= \left( \begin{array}{r}
Q_J \\
Q_{J'} \end{array} \right) $, and set

\begin{displaymath}{\cal N}^{(J)}_Q := \{ T \in \mbox{Mat} (k,r\!-\!k;R) \mid {\cal M}(U_TQ) \subseteq
{\cal M}(Q) \}. \end{displaymath}

Because $ U_T Q = \left( \begin{array}{c}
Q_J + TQ_{J'} \\
\end{array} \right)
$ and $
{\cal M}(U_T Q)= \langle Q_J + TQ_{J'} \rangle \subseteq {\cal M}(Q) =
\langle Q_J \rangle
$ if and only if $
\langle TQ_{J'} \rangle \subseteq \langle Q_J \rangle
$, we obtain:

\begin{displaymath}{\cal N}^{(J)}_Q = \{ T \in \mbox{Mat} (k,r\!-\!k;R)\ \mid \ ...
...T} \in \mbox{Mat} (n,n;R):
\ TQ_{J'} - Q_J \tilde {T} = 0 \}.

Choose a basis $ T_1, \ldots ,T_N $ of the module $ {\cal N}_Q^{(J)} $ and a set of associated matrices $ \tilde T_1 , \ldots , \tilde T_N \in
\mbox{Mat} (n,n;R)$.

Proposition 9 ((sufficient condition for J-row-minimality))  
Q is J-row-minimal if either
(i1) $ \tilde T_1, \ldots , \tilde T_N $ do not have a unit entry; i.e., $ \tilde T_i \, \mbox{mod}\; \underline{m} = 0 $
(i2) for any $ T \in {\cal N}^{(J)}_Q $, the corresponding matrix $\tilde T$ satisfies the condition: $ \tilde T \, \mbox{mod} \; \underline{m} $ is nilpotent.

Condition (i1) implies (i2). Assuming (i2), we obtain for any $ T \in {\cal N}_Q^{(J)} $

\begin{eqnarray*}{\cal M}(U_TQ) & = &
\langle Q_J + TQ_{J'} \rangle = \langle ...
...Q_J (I + \tilde T) \rangle = \langle Q_J \rangle = {\cal M}(Q),

because $ I + \tilde T $ is invertible. Therefore Q is J-row-minimal.


(5.2) In order to obtain a necessary condition for row-minimality, we have to improve the choice of a good representative $ \tilde Q $ in the equivalence class of Q, cf. (3.3). Write $ \tilde Q $ in block form

\begin{displaymath}\tilde Q = \left( \begin{array}{rr}
A & 0 \\
C & D
\end{array} \right),
\qquad A \in \mbox{Mat} (k,l).

We may assume that the columns of A form a completely reduced, minimal basis of $ {\cal M}(Q) $. This means the columns of A form a minimal system of generators, increasingly ordered, and the l-th generator is reduced with respect to the standard basis generated by the first l-1 generators for appropriate l.

Lemma 10   Let Q be a submodule of Rk, given by a completely reduced, minimal basis $A=(\underline{a}_1,\ldots,\underline{a}_r)$. A submodule P of Q is proper if and only if lead(P), the initial module, does not contain all leading terms of A.

We want to show that for a proper submodule P the minimal leading term not contained in lead(Q) must be in lead(A). Assume the contrary; i.e. the minimal $lead(\underline{q}_*)=q \underline{e}_l\not\in P$ is not contained in lead(A). We introduce the module $S= \langle m \underline{e}_s\vert m\underline{e}_s> q\underline{e}_l \rangle$, generated by all monomials in Rk which are greater than $q \underline{e}_l$.

Considering the whole situation in the factor module Rn/S, we have the equation

\begin{displaymath}q\underline{e}_l=\sum_i g_i \underline{a}_i,\end{displaymath}

and, from the assumption on reducedness, it follows that all gi belong to the maximal ideal ${\underline m} $. The staircases of both modules Q and P are identical up to $q \underline{e}_l$, and, hence, for every generator $\underline{a}_i$ an equation

\begin{displaymath}\underline{a}_i=\sum_k h_{ik} \underline{p}_k + c_i q\underline{e}_l\end{displaymath}

with $c_i\in K$ exists. We obtain

\begin{displaymath}q\underline{e}_l=\sum_{i,k} g_i h_{ik} \underline{p}_k + \sum_i g_i c_i q\underline{e}_l.\end{displaymath}

The second summand vanishes in Rn/S. Thus, $q \underline{e}_l$ must be a leading term of P, too.

The other implication is a well-known fact about standard basis.


(5.3) Without loss of generality we will assume that $ Q= \tilde Q =
\left( \begin{array}{rr}
A & 0 \\
C & D
\end{array} \right) $ fulfills the conditions of (5.2). For $ T \in {\cal N}^{(J)}_Q $ we obtain $ U_TQ = \left( \begin{array}{cc}
A+TC & TD \\
C & D \end{array} \right)
$ and $
\langle TC \rangle + \langle TD \rangle \subseteq
\langle A \rangle .
$ Therefore, matrices $ \tilde T' \in \mbox{Mat} (l,l;R)$

next up previous
Next: 6. Finding a J-row-reduction Up: Splitting algorithm for vector Previous: 4. Splitting criteria
| ZCA Home | Reports |