Kernel and Null Space Bases

[Rob Beezer]

A question about computing bases for kernels or null spaces of
matrices.

When working with students studying linear algebra for the first time,
I like to construct basis vectors for the (right) kernel by working
through the indices of the non-pivot columns of the reduced row
echelon form of the matrix, setting these entries to zero, with the
exception of one entry that is set to 1. Then the other entries are
just negatives of certain entries of the echelon form matrix.

This very approach is used (on the transpose) to compute the (left)
kernel. But then it gets used in the constructor of a subspace, which
calls a submodule constructor, which "echelonizes" the basis
(presumably to achieve some canonical representation). This means the
kernel produces a vector space with a very nice basis, but my students
won't recognize it. I'd like to get the pivot/non-pivot basis back.

Could the construction of the pivot/non-pivot basis be isolated from
the kernel() code in matrix2.pyx? And maybe called nullspace_basis
() or something similar? Then kernel() could call this method on the
transpose, and use the result to construct the subspace.

[William Stein]

That's a great idea.

I just looked at the kernel code in matrix2.pyx. Currently there is
only left_kernel and right_kernel. I notice with bemusement that
*both* functions transpose their input then do something! Pretty
stupid.

I think the right change for your application would be to change this
line in left_kernel:

W = V.submodule(basis)

to

if echelonize:
W = V.submodule(basis)
else:
W = V.submodule_with_basis(basis)

then put an echelonize=True option in the left_kernel function header.

William

-- William

[Rob Beezer]

William,

Thanks for the reply. I hadn't dug deep enough to find the
"with_basis" variant of the submodule constructor, so I like the
suggested approach. Barring anymore significant conversation here,
I'll take on submitting this with a ticket and a patch. It'll be a
learning experience for me (and make more work for Michael to guide me
through the contribution process). ;-)

Rob

[William Stein]

On Wed, Jan 28, 2009 at 3:55 PM, Rob Beezer <goo...@beezer.cotse.net> wrote:
>
> William,
>
> Thanks for the reply. I hadn't dug deep enough to find the
> "with_basis" variant of the submodule constructor, so I like the
> suggested approach. Barring anymore significant conversation here,
> I'll take on submitting this with a ticket and a patch. It'll be a
> learning experience for me (and make more work for Michael to guide me
> through the contribution process). ;-)

Well feel free to post here too when you have trouble, so that the process
gets documented (which is always good).

William

[Jason Grout]

Rob Beezer wrote:
> William,

>>
>> I think the right change for your application would be to change this
>> line in left_kernel:
>>
>> W = V.submodule(basis)
>>
>> to
>>
>> if echelonize:
>> W = V.submodule(basis)
>> else:
>> W = V.submodule_with_basis(basis)
>>
>> then put an echelonize=True option in the left_kernel function header.
>>
>> William
>>

Just FYI, I think there is still an issue sometimes when using
user-defined bases:

http://trac.sagemath.org/sage_trac/ticket/3058

Jason

[Rob Beezer]

I've added this into Trac.

http://trac.sagemath.org/sage_trac/ticket/5135

Jason - thanks for the heads-up on 3058.

William - someplace you *have* to turn rows into columns. ;-) In my
book, I think it is all buried into "column space of A = row space of
transpose(A)" or something similar. Would it be worthwhile to move
most of the basis construction into right_kernel()? Right now, a call
to right_kernel() does two transposes. With a change, left_kernel()
would still do a transpose, but then call right_kernel(). kernel()
could then be a call to left_kernel().

[Rob Beezer]

I've added this into Trac.

http://trac.sagemath.org/sage_trac/ticket/5135

Jason - thanks for the heads-up on 3058.

William - someplace you *have* to turn rows into columns. ;-) In my
book, I think it is all buried into "column space of A = row space of
transpose(A)" or something similar. Would it be worthwhile to move
most of the basis construction into right_kernel()? Right now, a call
to right_kernel() does two transposes. With a change, left_kernel()
would still do a transpose, but then call right_kernel(). kernel()
could then be a call to left_kernel().

On Jan 28, 4:24 pm, Jason Grout <jason-s...@creativetrax.com> wrote: