Companion matrix constructor

[rbeezer]

This will be used to construct the output of an upcoming rational canonical form.

Apply:

1. attachment: trac_11356-companion-matrix-v4.patch

CC: @sagetrac-fidelbarrera

Component: linear algebra

Keywords: sd31

Author: Rob Beezer

Reviewer: David Loeffler

Merged: sage-4.7.2.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/11356

[rbeezer]

Attachment: trac_11356-companion-matrix.patch.gz

[rbeezer]

Author: Rob Beezer

[jasongrout]

comment:2

Note that Magma defaults to format='bottom', I think. Is there any consistency issues with us defaulting to format='right', given that we follow the Magma convention of row vectors?

[jasongrout]

comment:3

Reference: http://wiki.sagemath.org/magma#Miscpolyfunctions

[rbeezer]

comment:4

Replying to @jasongrout:

Note that Magma defaults to format='bottom', I think. Is there any consistency issues with us defaulting to format='right', given that we follow the Magma convention of row vectors?

Everything I read about companion matrices and rational canonical form (Frobenius form) uses the "right" version. It is the natural thing to use when you put your basis vectors into a matrix as columns, as is done with QR, Jordan form, and maybe others.

So I think "right" is the right default (pun intended), but "bottom" (and "top" and "left") are available for folks constructing less natural objects.

[jasongrout]

comment:5

Replying to @rbeezer:

Replying to @jasongrout:

Note that Magma defaults to format='bottom', I think. Is there any consistency issues with us defaulting to format='right', given that we follow the Magma convention of row vectors?

Everything I read about companion matrices and rational canonical form (Frobenius form) uses the "right" version. It is the natural thing to use when you put your basis vectors into a matrix as columns, as is done with QR, Jordan form, and maybe others.

Yes, and my point is that since we follow the magma convention of putting basis vectors in rows, do we need to be consistent with their convention of format='bottom'?
And yes, I've also always seen it with format='right' as well.

[rbeezer]

comment:6

Replying to @jasongrout:

Yes, and my point is that since we follow the magma convention of putting basis vectors in rows, do we need to be consistent with their convention of format='bottom'?
And yes, I've also always seen it with format='right' as well.

And my point is that "follow the convention" is stronger than the reality. I like to say Sage has a "preference" for rows. The RDF/CDF decompositions return basis vectors in columns, Jordan form returns basis vectors in columns and I'm sure I can find more. So, if I can get a basis to convert to rational canonical form, then "right" will be the correct choice. I think this is a place where consistency for other decompositions is to be preferred.

Besides the overwhelming use of "right" in the literature. I would rather not look oddball to newcomers, just to be consistent with a language with a miniscule audience.

Rob

[rbeezer]

Attachment: trac_11356-companion-matrix-v2.patch.gz

[rbeezer]

comment:7

This needed rebasing, which is now the v2 patch.

[dandrake]

comment:8

Perhaps you should add a little suggestion for converting a symbolic polynomial to the kind of list this function needs; something like:

sage: x = var('x'); sympoly = x^3 + 2*x + 5
sage: parent(sympoly)
Symbolic Ring
sage: coefflist = [sympoly(x=0)] + [sympoly.coeff(x^k) for k in [1..sympoly.degree(x)]]; coefflist
[5, 2, 0, 1]
sage: companion_matrix(coefflist)
...whatever...

(One might be tempted to use .coeffs(x), but that leaves out zero coefficients.)

[rbeezer]

comment:9

Replying to @dandrake:

Perhaps you should add a little suggestion for converting a symbolic polynomial to the kind of list this function needs; something like:

Excellent idea.

[rbeezer]

Changed keywords from none to sd31

[rbeezer]

comment:10

Replying to @dandrake:

Perhaps you should add a little suggestion for converting a symbolic polynomial to the kind of list this function needs; something like:

Doctest section about symbolic polynomials has been expanded to reflect Dan's suggestion, and incorporated into a standalone v3 patch. Thanks for the suggestion, Dan.

[dandrake]

comment:11

Replying to @rbeezer:

Doctest section about symbolic polynomials has been expanded to reflect Dan's suggestion, and incorporated into a standalone v3 patch. Thanks for the suggestion, Dan.

Uh oh, your v2 and v3 patches seem identical...

[rbeezer]

comment:12

Attachment: trac_11356-companion-matrix-v3.patch.gz

Replying to @dandrake:

Uh oh, your v2 and v3 patches seem identical...

Must've forgotten an hg qrefresh. Sorry for the hassle.

Replaced the v3 patch with one that should be different than v2. Thanks for the catch.

[dandrake]

comment:13

If you feed companion_matrix the empty list, it complains about an IndexError. I'd rather see it:

• return the empty matrix, or
• change line 2839 to if n == 0 or or not poly[n] == 1: so that the ValueError actually gets raised.

Returning the empty matrix seems about right, but I can imagine people having strong opinions about the zero polynomial not being monic. I don't know about the conventions in this corner case, so do whatever seems best.

[rbeezer]

comment:14

Attachment: trac_11356-companion-matrix-v4.patch.gz

Replying to @dandrake:

Thanks, Dan.

Seems like an input list of [1] should be a monic polynomial that creates an empty matrix. Code does that before latest patch and a test of this has been added in the v4 patch.

So I made an input empty list fail in the v4 patch and added a test. In this case, n = -1, so various existing array references will fail, thus requiring its own error message. I tried to build an "empty polynomial" from an empty list, but just got the zero polynomial. So I think an empty list is the only danger, thus the error message reads this way.

[rbeezer]

comment:15

Forgot to set this as "needs review" when I put up the v4 patch.

[loefflerd]

comment:16

This looks great -- code is very clear and thorough with full documentation and tests, all of which pass. Positive review.

[rbeezer]

comment:17

Replying to @loefflerd:

Thanks, David, for taking the time to look at this. -Rob

[jdemeyer]

Reviewer: David Loeffler

[jdemeyer]

Merged: sage-4.7.2.alpha1