#14972: charpoly name clashes with matrix content
----------------------------------+--------------------------
Reporter: gagern | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-5.12
Component: linear algebra | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Dependencies:
Stopgaps: |
----------------------------------+--------------------------
Description changed by gagern:
Old description:
> ''This is a spin-off from #14403, to get that one landed and have a
> discussion with a wider scope here.''
>
> == Problem
>
> `matrix.charpoly()` will return a polynomial in a polynomial ring over
> `x`. That variable name is always used, unless overridden by an argument
> provided by the user. This is OK in many cases, but can become confusing
> or outright dangerous in cases where `x` already occursd inside the
> matrix, since in those cases there would be two occurrences of `x` with
> different semantics:
>
> {{{
> sage: x = var('x')
> sage: R = SR
> sage: matrix(R,2,2,[x,1,1,x]).charpoly()
> x^2 - 2*x*x + x^2 - 1
> sage: R.<x> = QQ[]
> sage: matrix(R,2,2,[x,1,1,x]).charpoly()
> x^2 - 2*x*x + x^2 - 1
> sage: R.<x> = FiniteField(4)
> sage: matrix(R,2,2,[x,1,1,x]).charpoly()
> x^2 + x
> sage: R.<x> = PowerSeriesRing(QQ)
> sage: matrix(R,2,2,[x,1,1,x]).charpoly()
> x^2 - 2*x*x - 1 + x^2
> }}}
>
> It is easy to see that this kind of result can be confusing to say the
> least. The data structure returned is a polynomial over the ring of the
> matrix, so the coefficients are all right. Any piece of code only
> interested in the list of coefficients shouldn't have to bother. But even
> code could encounter trouble if it were to pass this to some other
> application or library using a string-like representation, like this:
>
> {{{
> sage: R.<x> = QQ[]
> sage: y = var('y')
> sage: (matrix(R,2,2,[x,1,1,x]).charpoly()*(1 + y))
> -y - 1
> sage: (matrix(R,2,2,[x,1,1,x]).charpoly('t')*(1 + y))
> (y + 1)*((t - 2*x)*t + x^2 - 1)
> }}}
>
> As you can see, the distinction between the two flavours of `x` can
> easily get lost, e.g. by (deliberate or accidential) coercion into the
> symbolic ring. The real problem here is not so much the fact that this
> does not work (after all, the user ''could'' have chosen a different
> variable name in the first place), but rather that this will seem to work
> but will yield wrong results.
>
> == Proposal
>
> For this reason, I am of the strong opinion that `charpoly` (and perhaps
> other polynomial-returning functions as well, so if you know any, please
> point them out) should take some care to choose a non-clashing name.
>
> To implement this, we'd need a general method to recursively enumerate
> all names occuring in a set of values from a given ring. For most rings a
> complete list of generators would probably be appropriate, no matter
> whether they actually occur. For the symbolic ring I'd prefer to only use
> those which actually occur, since otherwise the current default of `x`
> would probably never be chosen for symbolic matrices, causing an
> unexpected difference in behavior.
>
> Given a list of symbol names, we could then try to come up with a non-
> clashing one. The most elaborate scheme would try some well-known symbols
> first, like `['x', 'y', 'z', 't', 'u', 'mu']`, before using indexed ones
> like `['x1', 'x2', …]`, until a locally unique one has been found. Of
> course one could omit the former, and use `SR.symbol()` instead of the
> latter, but the consequence would be that the default charpoly of a given
> matrix would not depend on this matrix alone, but also on which other
> computations have been done before. Plus those names are harder to read.
> So I'd rather avoid this approach.
>
> == Unsatisfied expectations
>
> Some users might be confused by the unexpected and perhaps unintuitive
> name of the variable. Compared with the confusion caused by the clashing
> names, I consider this acceptable.
>
> In comment:10:ticket:14403, nbruin pointed out that one might expect
>
> {{{
> charpoly(A)*charpoly(B) == charpoly(block_diagonal(A,B))
> }}}
>
> but this would no longer be universally true after this change. I
> consider this acceptable, since the result would not be an incorrect
> computation but instead an exception thrown due to a multiplication
> between incompatible rings. Faced with this, users could always augment
> their calls to
>
> {{{
> charpoly(A,'t')*charpoly(B,'t') == charpoly(block_diagonal(A,B),'t')
> }}}
>
> for some non-clashing variable name `t`.
New description:
''This is a spin-off from #14403, to get that one landed and have a
discussion with a wider scope here.''
== Problem
`matrix.charpoly()` will return a polynomial in a polynomial ring over
`x`. That variable name is always used, unless overridden by an argument
provided by the user. This is OK in many cases, but can become confusing
or outright dangerous in cases where `x` already occursd inside the
matrix, since in those cases there would be two occurrences of `x` with
different semantics:
{{{
sage: x = var('x')
sage: R = SR
sage: matrix(R,2,2,[x,1,1,x]).charpoly()
x^2 - 2*x*x + x^2 - 1
sage: R.<x> = QQ[]
sage: matrix(R,2,2,[x,1,1,x]).charpoly()
x^2 - 2*x*x + x^2 - 1
sage: R.<x> = FiniteField(4)
sage: matrix(R,2,2,[x,1,1,x]).charpoly()
x^2 + x
sage: R.<x> = PowerSeriesRing(QQ)
sage: matrix(R,2,2,[x,1,1,x]).charpoly()
x^2 - 2*x*x - 1 + x^2
}}}
It is easy to see that this kind of result can be confusing to say the
least. The data structure returned is a polynomial over the ring of the
matrix, so the coefficients are all right. Any piece of code only
interested in the list of coefficients shouldn't have to bother. But even
code could encounter trouble if it were to pass this to some other
application or library using a string-like representation, like this:
{{{
sage: R.<x> = QQ[]
sage: y = var('y')
sage: (matrix(R,2,2,[x,1,1,x]).charpoly()*(1 + y))
-y - 1
sage: (matrix(R,2,2,[x,1,1,x]).charpoly('t')*(1 + y))
(y + 1)*((t - 2*x)*t + x^2 - 1)
}}}
As you can see, the distinction between the two flavours of `x` can easily
get lost, e.g. by (deliberate or accidential) coercion into the symbolic
ring. The real problem here is not so much the fact that this does not
work (after all, the user ''could'' have chosen a different variable name
in the first place), but rather that this will seem to work but will yield
wrong results.
== Proposal
For this reason, I am of the strong opinion that `charpoly` (and perhaps
other polynomial-returning functions as well, so if you know any, please
point them out) should take some care to choose a non-clashing name.
To implement this, we'd need a general method to recursively enumerate all
names occuring in a set of values from a given ring. For most rings a
complete list of generators would probably be appropriate, no matter
whether they actually occur. For the symbolic ring I'd prefer to only use
those which actually occur, since otherwise the current default of `x`
would probably never be chosen for symbolic matrices, causing an
unexpected difference in behavior.
Given a list of symbol names, we could then try to come up with a non-
clashing one. The most elaborate scheme would try some well-known symbols
first, like `['x', 'y', 'z', 't', 'u', 'mu']`, before using indexed ones
like `['x1', 'x2', …]`, until a locally unique one has been found. Of
course one could omit the former, and use `SR.symbol()` instead of the
latter, but the consequence would be that the default charpoly of a given
matrix would not depend on this matrix alone, but also on which other
computations have been done before. Plus those names are harder to read.
So I'd rather avoid this approach.
== Unsatisfied expectations
Some users might be confused by the unexpected and perhaps unintuitive
name of the variable. Compared with the confusion caused by the clashing
names, I consider this acceptable.
In comment:10:ticket:14403, nbruin pointed out that one might expect
{{{
charpoly(A)*charpoly(B) == charpoly(block_diagonal(A,B))
}}}
but this would no longer be universally true after this change. I consider
this acceptable, since the result would not be an incorrect computation
but instead an exception thrown due to a multiplication between
incompatible rings. Faced with this, users could always augment their
calls to
{{{
charpoly(A,'t')*charpoly(B,'t') == charpoly(block_diagonal(A,B),'t')
}}}
for some non-clashing variable name `t`.
In comment:17:ticket:14403, burcin stated that a method to obtain new
variable names should operate in constant time, everything else being to
complicated. I agree that constant time would be desirable for all those
cases where the variable name really doesn't matter, i.e. where the
polynomial is only used internally, as a list of coefficients no mater the
variable name. But wherever the polynomial might end in the hands of the
user, I think a bit more work is warranted.
I wonder whether it would be feasible to always explicitely state any
variable name in the internal calls, thus avoiding the automatic
selection, and leave the default argument case to users only. This would
mean going over the whole codebase and replacing all calls of
`.charpoly()` by `charpoly('x')`, all calls of `charpoly(*)` by
`charpoly(*, 'x')`, and likewise for `characteristic_polynomial`. The non-
method versions might be difficult to express in terms of regular
expressions, but grepping for `charpoly` should highlight all use cases,
and editor macros with a fall back to manual editing should see them
adjusted.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/14972#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
