Determinant or matrix from symbolic equation

Suppose as an example we have 6 symbolic variables,

syms a b c d e f

We have an expression

a*b*d*e^3-a^2*c^3*d+b^2*e*f*a*b+a*b*c*d*e*f -c^3*d^3-a*b*d^3*f +2*5*7^2*1*5

I would like to construct a matrix or determinant of any order or rank or rows or columns such that the determinant of that matrix gives the expression. For example b^2-ac may be expressed as [b,a;c,b]. The elements should be as simple as possible. Example instead of [c*b,a*f;c*d,b*e] matrix should be like [a,f,1;e,b,f]. The individual elements shall be as simple as possible

[Walter Roberson]

Note that because you have variables up to power 3, you have the choice between making the matrix elements have powers, with a smaller matrix, or having a larger matrix in which there are duplicate variables. You indicate that the individual elements should be as simple as possible: could you confirm that you would be fine with using a larger matrix in order to reduce the complexity of the individual elements of the matrix?

b^2*e*f*a*b
a*b*c*d*e*f
c^3*d^3

All three of those are total degree 6. Making the elements as simple as possible would lead to a matrix that was at least 6 x 6L could you confirm that is acceptable compared to using a smaller matrix in which there might be multiplications or higher powers?

[Saikat Banerjee]

I presume by 6L you are referring to 6 Lakhs. No then its an impractical solution. The objective is to make each element as simple as possible keeping in mind practicalness so that it does not takes one hour to compute. As a principal you can give me a number of matrices with each element of the matrix having highest degrees of 1,2,3,4,5and 6. For example 1st matrix may be [a,c,f;b,d,e], 2nd matrix may be [a^2,d*d;f^2,c*e], and 3rd matrix may be [a^3,a*d*f;d^3,a*b^2] and so on

[Walter Roberson]

Heh, no, 6 x 6L was just a typing mistake for 6 x 6.

[Walter Roberson]

Sorry, at the moment no organized way of solving this is coming to mind.

[John D'Errico]

In fact, this is probably some sort of exponential time problem, requiring you to try essentially all possible matrices that are low order in the elements. And since an nxn matrix has n*n elements, you are talking about a highly computationally nasty problem.

Wanting to do something is fine. Hoping for an easy solution in the face of all odds is highly optimistic.

[Walter Roberson]

5567902560 possibilities I figure. Excluding symmetry arguments, and those arguments are valid ones, so with some care you could probably reduce to 1/4 of that. Possibly even 1/720 of that.

[John D'Errico]

I get a different, larger number. Each element in the matrix can be any one of: {a,b,c,d,e,f,0,1}. That does not even include other possibilities, like what is one of the elements had to be some OTHER number? 0, 2, -1? In that case, the number of possibilities will grow rapidly. But supposing any element in the 6x6 matrix could be any of those 8 possibilities? If so, then the total number of matrices to check would logically be

8^36
ans =
      3.24518553658427e+32

As I said, this gets way worse of a term could be be any of the integers -5:5, for example. Now you might need to conider as many as

17^36
ans =
      1.97770344305989e+44

posssible matrices.

That number gets smaller due to symmetries of course, but not too much smaller. Thus simple diagonal relfections allow you to reduce it by a factor of 4. Now we are talking. But also, we can allow row exchanges. Thus exchange any two rows, and the determinant gets multiplied by a factor of -1. So swap TWO pairs of rows, and it comes back. Also, you can swap pairs of columns.

How many pairs of rows are there?

nchoosek(6,2)
ans =
    15

So there are 15 pairs of rows we can swap. thus 30 possible choices of rows OR columns. And we need to select either 2 row/column swaps, oe 4 row/column swaps, or 6 column swaps, etc.

Again, while this is a reduction of the total number of possible matrices we would need to inspect, the count is still huge. And every such text will require the computation of a symbolic 6x6 determinant.

Not a small problem.

[Walter Roberson]

The various elements have power no more than 3, and 1, 2, 5, and 7 occur. So it is potentially possible that the determinant could occur from arranging the 21 elements [a, a, b, b, b, c, c, c, d, d, d, e, e, e, f, 1, 2, 5, 5, 7, 7] in a 6 x 6 matrix with the remaining elements 0. That is 36!/21!/15! arrangements... potentially reducible by several factors by symmetry and substitution of variables for each other . Ah, I forgot to reduce by duplicates, so divide by 2! 3! 3! 3! 3! 2! 2! .

Still a big number.

The determinant of the 6 x 6 could be computed once, a vector of 720 additions, and then subs() the actual values in for the nominal variables.

[Saikat Banerjee]

There is one big misunderstanding. The symbolic variables are a..f. Apart from that there can be any rational no from -inf to +inf.

[Walter Roberson]

The question is to find a matrix whose determinant is the expression given, with the intention that the entries be "as simple as possible". Determinants require square matrices.

It is a hypothesis that this can be done with a matrix that has the same number of rows (and columns) as the number of distinct symbols in the expression (hypothesizing that the constants do not need additional rows or columns to enter into the determinant.)

There are 6 unique variables, so the hypothesis is that there are 6 x 6 = 36 values to be determined, the matrix entries whose determinant is the given expression.

Because the various entries interact with each other, hypothesizing a value for one of the 36 entries constrains some of the other values for consistency with the required determinant, so knowing some of the 36 can force other of the 36 to be either 0 or 1.

[Walter Roberson]

John: What if we took advantage of the fact that no minimization of the size of the matrix has been imposed, as long as the entries are "as simple as possible" ?

Suppose for example we started by breaking the expressions into terms and putting the terms along diagonals:

 a
-a b
 b a d
 a b c e
-c b e c e
-a c c f c e
 2 b c d a d 1
 ? 5 d d e b 1 1
 ? ? 5 d d f 1 1 1
 ? ? ? 7 d d 1 1 1 1
 ? ? ? ? 7 f d 1 1 1 1
 ? ? ? ? ? 1 1 1 1 1 1 1

Then because the permutations that occur will include the diagonals (as a subset), all of the original terms will occur "as is" in the determinant.

Now by filling out with 0's can we prevent any other term of the determinant from having non-zero value? Even if it requires enlarging the matrix with a selection of 1's and 0's? My intuition is that it could done with at most 7 * 2^7 rows / columns to act as selectors (and quite possibly fewer.)

[Saikat Banerjee]

Try this approach and write a program

Answer 1

[Saikat Banerjee]

I think you all are going in impossible directions. Even Google's supercomputers wont be able to solve this problem then. Let it bring it down to simplistic small amount of finite equations. Let individual elements of solution matrix be x(i,j). Where i = 1 to 6 j = 1 to 6. Now compute the determinants and compare with the original equation. You will get a finite no of equation and probably a solution. Also you can compare co-efficients. Try this approach

[Walter Roberson]

The determinant has 720 terms in 36 variables, which has to be compared to the 7 additive terms in 6 variables. You can hypothesize a term match such as a*b*d*e^3 == x11*x26*x34*x45*x52*x63 and solve for one of the 36 variables, and substitute the resulting variable into the list of 720 terms.

Having done that, you can look at the resulting list and find the ones that can no longer match because they would duplicate the e^3 term (which occurs only once. Each of those will involve some x terms that have not been dealt with yet. Pick one of them and hypothesize that it is 0 (in order to zero out the e^3 term), substitute that in, go on to the next term that still has an e^3, pick one of the x's from that, hypothesize it is 0, substitute, and so on, until you have reached a hypothesis of zero for a number of x terms that brings the overall sum into agreement with the e^3 terms. You can do this.

But... what if one of those hypotheses was wrong, and leads to a situation in which some other terms cannot match? Then you need to withdraw the hypothesis and go on to the next hypothesis there. And you will almost certainly get to the point where all of the terminal hypotheses fail and you have to go back and revoke an earlier hypothesis.

So to do this work, as well has writing the intelligent pattern matching logic, you have to have a robust multi-level backtracking system that can deal with about 36 levels of backtracking.

Mechanically possible? Probably. Length of time that it would take to find a solution... rather large !!!

A brute force solution that will work theoretically but in practice will take several decades, is not a realistic solution.