       Re: A few questions about RowReduce - bis

• To: mathgroup at smc.vnet.net
• Subject: [mg24256] Re: [mg24074] A few questions about RowReduce - bis
• From: Murray Eisenberg <murray at math.umass.edu>
• Date: Wed, 5 Jul 2000 23:10:37 -0400 (EDT)
• Organization: Mathematics & Statistics, Univ. of Mass./Amherst
• References: <8j9dsq\$51v@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```A reason to find a row-echelon form that is not the canonical "reduced"
row-echelon form, is that you can answer questions about the nature of
solutions of linear systems, or linear independence of vectors, etc.,
without having to do -- or asking Mathematica to do -- all the extra
work to get the reduced row-echelon form.

Preston Nichols wrote:
>
> Jack-Michel,
>
> Here are some ideas which I hope will be helpful, though they do not
>  (To be honest, I can't think of why that specific form would be
> essential.)  My discussion focuses on equations for the image of a matrix.
>
>
> In:= n = 5;
>         m = Table[(i + j - 1)^2, {i, n}, {j, n}];
>
> A vector of variables (note I changed yi from you message to y[i]):
>
> In:= v = Table[y[i], {i, n}];
>
> The same structure can be built this way:
>
> In:= v = Array[y,n];
>
> The vector v appended to m as the last column:
>
> In:= << "LinearAlgebra`MatrixManipulation`";
>         mv = AppendRows[m, Transpose[{v}]]
>
> The same operation, without requiring the MatrixManipulation package:
>
> In:= mv = Transpose[Append[Transpose[m], v]]
>
> RowReduce[mv] permits division by polynomials in the y-variables, even
> though such expression may have the value zero.  Row-reduction of mv,
> treating the y-variables as generic, leads to (from your own Mathematica
> function):
>
> {{1,  4,   9,   16,   25, y},
>  {0, -7, -20,  -39,  -64, -4y + y},
>  {0,  0, 8/7, 24/7, 48/7, (17*y)/7 - (20*y)/7 + y},
>  {0,  0,   0,    0,    0, -y + 3*y - 3*y + y},
>  {0,  0,   0,    0,    0, -3*y + 8*y - 6*y + y}}
>
> from which can be extracted equations for the image of the matrix:
>
> -y + 3 y - 3 y + y==0,
> -3 y + 8 y - 6 y + y==0
>
> One of your questions is how to get Mathematica to perform such a
> calculation.  I found three ways, each having its own interest.
>
> ====================================================
>
> Mathematica solution 1:  The "Left Nullspace"
>
> In:= leftnullspace = NullSpace[Transpose[m]]
>
> Out= {{-3, 8, -6, 0, 1}, {-1, 3, -3, 1, 0}}
>
> These vectors span the orthogonal complement of the image of m, so by
> setting dot products with v to zero, you can recover the desired equations.
>
>
> Out= {-3 y + 8 y - 6 y + y == 0,
>          -y + 3 y - 3 y + y == 0}
>
> (Thread changes an "equation of lists" into a "list of equations".)
>
> This strikes me as "the right way", because (1) it is brief, using
> high-level built-in Mathematica functions, and (2) it relies on a
> fundamental theorem of finite-dimensional linear algebra.  An aphorism:
> Sometimes Mathematica does mathematics for you; sometimes you must do
> mathematics for Mathematica.
>
> ====================================================
>
> Mathematica solution 2:  Use Eliminate
>
> In:= ImageEquations[mat_?MatrixQ, y_Symbol] := Module[{m, n, x},
>     {m, n} = Dimensions[mat];
>     Eliminate[Thread[mat.Array[x, n] == Array[y, m]], Array[x, n]]
>     ]
>
> In:= ImageEquations[m, y]
>
> Out= y == 3 y - 3 y + y && y == 3 y - 3 y + y
>
> Note that this method returns equations, rather than vectors (of
> coefficients for the equations) as my other solutions do.
>
> To understand how this function works, examine the step-by-step output from
> input lines such as
>
> u = Array[x, n]
> v = Array[y, n]
>
> m.u == v
>
> Thread[%] (* "equation of lists" to "list of equations" again *)
>
> Eliminate[%, u]
>
> This may not always give exactly the same equations as the "left nullspace"
> method, but the difference is due only to a change of basis for the
> orthogonal space to the image of m.  Mathematically, the answers are
> equivalent.
>
> ====================================================
>
> Mathematica solution 3:  Use RowReduce after all!
>
> Here's a function which appends an IdentityMatrix of appropriate size to
> the right of the given matrix, and then applies RowReduce to the whole
> thing.  (This is what one does when using row operations to find the
> inverse of a square matrix, but it can be done, in principle, on any matrix.)
>
> Here's a version that makes use of LinearAlgebra`MatrixManipulation`:
>
> In:= doubleRowReduce[mat_?MatrixQ] :=
>   RowReduce[
>     AppendRows[mat, IdentityMatrix[First[Dimensions[mat]]]]
>     ]
>
> Here's a version of the same function that doesn't require the package:
>
> In:= doubleRowReduce[mat_?MatrixQ] :=
>   RowReduce[
>     ]
>
> The coefficients for the equations of the image of the matrix m appear at
> the right in the bottom rows of doubleRowReduce[m].  The rows to use are
> those which reduce to zeroes in m.  (I won't try to reproduce the output
> here; try it and see!)  You can think of the columns of the appended
> identity matrix as holding coefficients of the y-variables.  The original
> problem required a cummulative "record" of the arithmetical operations
> performed on each of the y[i]'s, so giving each y[i] a column of its own
> makes sense.
>
> Here's a function to extract the desired coefficients from the results of
> doubleRowReduce, using TakeMatrix from LinearAlgebra`MatrixManipulation.  I
> suspect this could be done in a better way, but it works:
>
> In:= imagecoefficients[mat_?MatrixQ] :=
>   With[{m = Length[mat], n = Length[First[mat]]},
>     TakeMatrix[mat,
>       {-Count[TakeColumns[mat, n - m], _?(Union[#] == {0} &)],
>         n - m + 1},
>       {-1, -1}
>       ]
>     ]
>
> In:= imagecoefficients[doubleRowReduce[m]]
>
> Out= {{1, 0, -6, 8, -3}, {0, 1, -3, 3, -1}}
>
> Again, this may not always give exactly the same equations as the other
> methods, but the difference is due only to a change of basis in the
> y-variables, leaving the image and its complementary space invariant.
>
> ====================================================
>
> I hope this is of some use for you.
>
> Preston Nichols
> Mathematics and Computer Science
> Wittenberg University
>
> At 02:26 AM 06/23/2000 -400, jmcornil wrote:
> >First question :  >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
> >
> >The function RowReduce perform a Gauss-Jordan reduction putting
> >1 on the "diagonal" and 0 elsewhere so long it is possible. But is there
> >an other function (or an option for RowReduce) performing a simple
> >Gauss reduction i.e. putting 0  ONLY UNDER the first diagonal ?
> >
> >By the way I saw there is an option "Method" for the function.
> >
> >In:= Options[RowReduce]
> >Out= {Method -> Automatic, Modulus -> 0, ZeroTest -> Automatic}
> >
> >and I did not found any help on it. How to use it ?
> >
> >Second question : >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
> >
> >I did not foud any function to perform a "limited" Gauss reduction, i.e.
> >a function performing
> >a reduction up to a column number .  Such an option woud be useful in a
> >case as follows
> >to get equations of the image of a matrice.
> >
> >In the following exampe, if you let RowReduce working as it will, you
> >also reduce the last column
> >(since formally the polynoms in  yi are not ZERO) and you cannot get the
> >equations of  image of the matrice.
> >
> >In:=n = 5;
> >            m = Table[(i + j - 1)^2, {i, n}, {j, n}];
> >           v = Table[yi, {i, n}];
> >            << "LinearAlgebra`MatrixManipulation`";
> >           mv = AppendRows[m, Transpose[{v}]]
> >Out=...
> >
> >In:=RowReduce[mv]
> >
> >Out=...
> >
> >Third and (last) question : >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
> >
> >So I qickly wrote some lines to get my aim.
> >But I am just beginning to program with Mathematica
> >and it is written as with Pascal and other classical languages.
> >Is ther a mean to write such a function using more pattern-matching ?
> >
> >gaussElim[m_, jmax_] :=
> >  Module[{},
> >    mm = m;
> >    nl = Dimensions[mm][];
> >    nc = Dimensions[mm][];
> >    For[i0 = 1; j0 = 1,
> >            i0 <= nl; j0 <= Min[nc, jmax],
> >             i0++ ; j0++ ,
> >            ip = i0;
> >            While[ip < nl && mm[[ip, j0]] == 0, ip++];
> >            If[mm[[ip, j0]] == 0, i0--; Continue[]];
> >
> >          {mm[[i0]], mm[[ip]]} = {mm[[ip]], mm[[i0]]};
> >
> >           For[i = i0 + 1,
> >                      i <= nl,
> >                      i++,
> >                       mm[[i]] = Simplify[mm[[i]] - mm[[i, j0]]/mm[[i0,
> >j0]]*mm[[i0]]]];
> >                  ];
> >      mm]
> >
> >In:= gaussElim[mv, 5]
> >Out= ...
> >
> >
> >Thanks very much for answer,
> >
> >Jack-Michel CORNIL
> >
> >VERSAILLES-FRANCE
> >

--
Murray Eisenberg                     murray at math.umass.edu
Mathematics & Statistics Dept.       phone 413 549-1020 (H)
Univ. of Massachusetts                     413 545-2859 (W)
Amherst, MA 01003-4515

```

• Prev by Date: Re: Drawing polytopes
• Next by Date: l'Hopital's Rule
• Previous by thread: Re: Piecewise functions definition and usage
• Next by thread: l'Hopital's Rule