## Finding one of many solutions to a big system of equations

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

### Finding one of many solutions to a big system of equations

I have a system of 21 equations in 35 variables and I'd like Maple to find a solution. Just one will do. However I rarely use Maple so I'm not sure how to get it to do this. fsolve complains when it has more variables than equations, and I can't seem to find any alternatives in the documentation. Moreover any other suggestions for solving this system are welcome. I used Maple because it was what I had on hand.

The equations are below:

Code: Select all
`> norm1 := a[1]^2+b[1]^2+c[1]^2+d[1]^2+e[1]^2 = 5;> norm2 := a[2]^2+b[2]^2+c[2]^2+d[2]^2+e[2]^2 = 5;> norm3 := a[3]^2+b[3]^2+c[3]^2+d[3]^2+e[3]^2 = 5;> norm4 := a[4]^2+b[4]^2+c[4]^2+d[4]^2+e[4]^2 = 5;> norm5 := a[5]^2+b[5]^2+c[5]^2+d[5]^2+e[5]^2 = 5;> norm6 := a[6]^2+b[6]^2+c[6]^2+d[6]^2+e[6]^2 = 5;> norm7 := a[7]^2+b[7]^2+c[7]^2+d[7]^2+e[7]^2 = 5;> dot13 := a[1]*a[3]+b[1]*b[3]+c[1]*c[3]+d[1]*d[3]+e[1]*e[3] = -2;> dot14 := a[1]*a[4]+b[1]*b[4]+c[1]*c[4]+d[1]*d[4]+e[1]*e[4] = -2;> dot15 := a[1]*a[5]+b[1]*b[5]+c[1]*c[5]+d[1]*d[5]+e[1]*e[5] = -2;> dot16 := a[1]*a[6]+b[1]*b[6]+c[1]*c[6]+d[1]*d[6]+e[1]*e[6] = -2;> dot24 := a[2]*a[4]+b[2]*b[4]+c[2]*c[4]+d[2]*d[4]+e[2]*e[4] = -2;> dot25 := a[2]*a[5]+b[2]*b[5]+c[2]*c[5]+d[2]*d[5]+e[2]*e[5] = -2;> dot26 := a[2]*a[6]+b[2]*b[6]+c[2]*c[6]+d[2]*d[6]+e[2]*e[6] = -2;> dot27 := a[2]*a[7]+b[2]*b[7]+c[2]*c[7]+d[2]*d[7]+e[2]*e[7] = -2;> dot35 := a[3]*a[5]+b[3]*b[5]+c[3]*c[5]+d[3]*d[5]+e[3]*e[5] = -2;> dot36 := a[3]*a[6]+b[3]*b[6]+c[3]*c[6]+d[3]*d[6]+e[3]*e[6] = -2;> dot37 := a[3]*a[7]+b[3]*b[7]+c[3]*c[7]+d[3]*d[7]+e[3]*e[7] = -2;> dot46 := a[4]*a[6]+b[4]*b[6]+c[4]*c[6]+d[4]*d[6]+e[4]*e[6] = -2;> dot47 := a[4]*a[7]+b[4]*b[7]+c[4]*c[7]+d[4]*d[7]+e[4]*e[7] = -2;> dot57 := a[5]*a[7]+b[5]*b[7]+c[5]*c[7]+d[5]*d[7]+e[5]*e[7] = -2;`

Thanks for any help.

Blatm

Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

### Re: Finding one of many solutions to a big system of equatio

Are you looking for an analytic solution, or will a numeric approximation do? Real or complex?

Here's an approach exploiting the problem symmetry that should at least give you a numeric solution; I haven't tried to see how ugly an analytic solution would get. First write
ti = <ai,bi,ci,di,ei> (i=1,...,7)
for the seven vectors in R5 (I'm assuming), and
T = [ t1 t2 ... t7 ]
for the 5*7 matrix. Now the 21 constraints can be written as a matrix equation,
Code: Select all
`         [   5   *  -2  -2  -2  -2   *  ]         [   *   5   *  -2  -2  -2  -2  ]         [  -2   *   5   *  -2  -2  -2  ]T' * T = [  -2  -2   *   5   *  -2  -2  ] = M         [  -2  -2  -2   *   5   *  -2  ]         [  -2  -2  -2  -2   *   5   *  ]         [   *  -2  -2  -2  -2   *   5  ]`
where the * are as-yet-undetermined. Now M is "almost Toeplitz" (i.e., apart from the possibly-different values *). If all of the * are equal, say to x, then the symmetric Toeplitz form of the matrix means that the eigenvalues, apart from the first one, will all appear in pairs. Note that if T is a solution, then so is R*T for orthogonal matrix R in O(7) (this corresponds to the freedom we have to rotate all of the ti by the same rotation matrix, preserving all of the dot-product constraints).

In order for a real 7*7 square root T to exist, M must be nonnegative. This happens for 3/2<=x<=1.88471 (the upper bound is the solution to a cubic).

Because we want T to have rank 5, M must have two zero eigenvalues. At x=3/2 there is a single zero eigenvalue, but at x~~1.88471 there is a double zero eigenvalue, so this is the value of x to use. Now take the matrix square root to get T, which should have rank 5. Use the rotational freedom R to rotate the column vectors into R5 (this still leaves you O(5) freedom). One solution I get this way (algebra via Mathematica) is
Code: Select all
`    [ 0.000000000     1.438239086     1.793454806     0.7981624769    -0.7981624769   -1.793454806    -1.438239086  ]    [ 1.839576838     1.146957398     -0.4093443561   -1.657401461    -1.657401461    -0.4093443561   1.146957398   ]T = [ 0.000000000     -1.196439857    0.5324658284    0.9594702698    -0.9594702693   -0.5324658288   1.196439856   ]    [ 1.227208537     -0.2730795897   -1.105676686    0.7651520074    0.7651520074    -1.105676686    -0.2730795897 ]    [ -0.3315362185   -0.3315362185   -0.3315362185   -0.3315362185   -0.3315362185   -0.3315362185   -0.3315362185 ]`

--

As an aside, I initially proved this was impossible, but I had misread your constraints: I thought you also had dot17 = -2, and with this additional constraint there are no (real) solutions.

eta oin shrdlu

Posts: 401
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: Finding one of many solutions to a big system of equatio

Thanks eta! This is great.

Blatm

Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

### Re: Finding one of many solutions to a big system of equatio

So I worked through an analytic solution; it turns out to be pretty straightforward. I think everything you need to know is here (the specific kind of Toeplitz matrix I used above is called a circulant matrix, and these are very easy to diagonalize, so there's not much algebra), but I can describe it if you have questions.

eta oin shrdlu

Posts: 401
Joined: Sat Jan 19, 2008 4:25 am UTC

### Re: Finding one of many solutions to a big system of equatio

This is related to coursework so I'd rather not talk too much about it now. After everything is submitted I'll get back to you.

Blatm

Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

### Who is online

Users browsing this forum: No registered users and 7 guests