id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
14972 charpoly name clashes with matrix content gagern "''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. = QQ[]
sage: matrix(R,2,2,[x,1,1,x]).charpoly()
x^2 - 2*x*x + x^2 - 1
sage: R. = FiniteField(4)
sage: matrix(R,2,2,[x,1,1,x]).charpoly()
x^2 + x
sage: R. = 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. = 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." defect new major sage-6.4 linear algebra N/A