Re: Minimal maximum eigenvalue in closed form?

• To: mathgroup at smc.vnet.net
• Subject: [mg58370] Re: [mg58315] Minimal maximum eigenvalue in closed form?
• From: Pratik Desai <pdesai1 at umbc.edu>
• Date: Tue, 28 Jun 2005 21:57:02 -0400 (EDT)
• References: <200506280913.FAA05092@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Paul Abbott wrote:

>Here is an interesting exercise: compute the minimal maximum eigenvalue
>of the matrix (arising in a semidefinite programming problem)
>
> mat =
> {
>  {1, 1 - x[4], 1 - x[4], 1 - x[4], 1, 1},
>  {1 - x[4], 1, 1 - x[5], -x[1] - x[5] + 1, 1 - x[5], 1},
>  {1 - x[4], 1 - x[5], 1, 1 - x[1] - x[6], 1 - x[2] - x[6], 1 - x[6]},
>  {1 - x[4], 1-x[1] -x[5], 1-x[1] -x[6], 1 - 2x[1], 1 - x[2], 1 - x[3]},
>  {1, 1 - x[5], -x[2] - x[6] + 1, 1 - x[2], 1 - 2x[2], 1 - x[3]},
>  {1, 1, 1 - x[6], 1 - x[3], 1 - x[3], 1 - 2x[3]}
> };
>
>in closed form. This is reminiscent of the sort of problems given in the
>SIAM 100 digit challenge, see
>
>  mathworld.wolfram.com/Hundred-DollarHundred-DigitChallengeProblems.html
>
>
>It can be shown that the exact answer can be expressed as the root of a
>6th order polynomial. Does anyone have an elegant way of obtaining the
>solution (and also the values of x[1] through x[6])?
>
>Cheers,
>Paul
>
>
>
Hi Paul,

Here is my somewhat lame attempt. Although I am not clear what minimal
maximum value means, perhaps Least Upper Bound and what is a closed form
solution in this case since you are calculating, in effect ,the roots of
a 6th order polynomial. Using NSolve I get the following,

Clear[mat,mat1]
<<LinearAlgebra`MatrixManipulation`
mat={{1,1-x[4],1-x[4],1-x[4],1,1},{1-x[4],1,1-x[5],-x[1]-x[5]+1,1-x[5],
1},{1-x[4],1-x[5],1,1-x[1]-x[6],1-x[2]-x[6],1-x[6]},{1-x[4],
1-x[1]-x[5],1-x[1]-x[6],1-2x[1],1-x[2],1-x[3]},{1,
1-x[5],-x[2]-x[6]+1,1-x[2],1-2x[2],1-x[3]},{1,1,1-x[6],1-x[3],
1-x[3],1-2x[3]}}/.{x[1]->Subscript[x,1],x[2]->Subscript[x,2],
x[3]->Subscript[x,3],x[4]->Subscript[x,4],x[5]->Subscript[x,5],
x[6]->Subscript[x,6]};
mat1=TakeMatrix[mat,{1,1},{6,6}]
expr2=\[Lambda] *IdentityMatrix[6]-mat1//Det;

Best regards
Pratik

--
Pratik Desai