# LinearSolve and LeastSquares giving different results on system with a solution

So I'm working on a program for my PhD which is supposed to do the following: Take a polynomial f, build a matrix A with Table[Coefficient[f[n*x + k + i - 1], x^j], {i, n}, {j, Deg}] (Deg is the degree of f, n is arbitrary positive integer), then take a function g of the same degree as f and construct a vector B with Table[Coefficient[g[x + m], x^j], {j, Deg}], then solve A.x = B for x in terms of k,m and then find at least one integer value of k,m so that each entry of x is nonnegative. If n = Deg then it's a square matrix and it's possible to show that A will always be invertible, and max rank if it's nonsquare.

But for some reason (for a specific case of f = x^3, g = (2x+1)^3) when A is 3x2 (i.e. Deg = 3, n = 2), using LeastSquares[Transpose[A],B] gives me the correct solution whereas LinearSolve[Transpose[A],B] tells me there is no solution, and when A is 3x4 (now for the case f = x^3, g = (4x+1)^3, Deg = 3, n = 4), the exact opposite happens. (Due to the nature of the problem, given any n I can choose f,g so that I know there is a solution for that n, and I know what one of the solutions is.)

EDIT: To clarify, both LinearSolve and LeastSquares give a solution for A.x = B, however when I try to find (k,m) so that the entries of x are all positive, for one of them I can find such a pair ((0,0) works for both, and I chose these functions so that it would be a solution), but for the other one it tells me there is no such pair.

I'm really confused because I looked at the documentation which explicitly says that if there is a solution, I should get the same result from both. And I wouldn't even be that bothered if one of them gave more or less correct solutions, since I only need one value of (k,m) for what I'm doing, but if I'm getting incorrect results in different cases then it's a bit of a problem.

• There is information missing. Is n set to 2? How does size of the matrix depend on a coefficient in g? Oct 14, 2020 at 19:28
• @DanielLichtblau the matrix A is Deg x n, sorry I didn't make that clear. And for the nature of the problem the degree of g must equal the degree of f, which is Deg. So when A is 3x2 n is 2, when A is 3x4 n is 4, in both cases Deg is 3. Oct 14, 2020 at 20:18
• Okay. The change in g threw me. You should edit the post to indicate clearly that you use those two specific values to attain the stated degrees. As for solutions, generically there are none when the system is overdetermined. Oct 14, 2020 at 20:27

## 1 Answer

You should mention that you are working with polynomials not arbitrary functions.

Then your example:

f[x_] := x^3; g[x_] := (2 x + 1)^3
n = 3; deg = 3;
a = Table[
Coefficient[f[n*x + k + i - 1], x^j], {i, n}, {j,
deg}]; a // MatrixForm
b = Table[Coefficient[g[x + m], x^j], {j, deg}]


Using Leastsquares:

Simplify[LeastSquares[Transpose[a], b], Assumptions -> k \[Element] Reals]


Using LinerSolve : LinearSolve[Transpose[a], b]

Could it be a problem with versions of MMA. I am using 12.1.

Note there seems to be no Integer k and m that make these expression non-negative

• The problem is when Deg = 3, n =2 or 4. If it's a square matrix there's never an issue since it will be invertible. Oct 14, 2020 at 20:19
• With n==4 both functions return a solution (MMA 12.1). With n==2 we have an overdetermined system. LeastSquares returns a solution, LinearSolve not. If I may speculate, the former can return an approximate solution, the later only an exact one. For overdetermined systems, there is no general solution, perhaps particular ones. It may be that LinearSolve only returns general solutions. Oct 15, 2020 at 9:35
• Sorry, I think I didn't explain my problem very well. You're right that they both give solutions for x when n = 4. The problem is that for one of these solutions, there is no value of (k,m) which makes x have all nonnegative entries, but for the other solution there is (namely, k = m = 0). The main goal here is not just to solve for x in Ax = B but to also make sure that I can find a pair (k,m) that makes all of the entries in x nonnegative. My fault for not being clearer on this. Oct 15, 2020 at 17:35