4
$\begingroup$

I have the following 4x4 real symmetric matrix:

$K=\begin{bmatrix}3-3w & -\frac{4}{3}+a+2w & \frac{5}{12}+b-\frac{w}{2} & 0\\ -\frac{4}{3}+a+2w & -1-6a-3x & \frac{3}{4}+3a-3b+2x-\frac{y}{2} & -\frac{2}{3}-a-\frac{x}{2}+\frac{z}{2}\\ \frac{5}{12}+b-\frac{w}{2} & \frac{3}{4}+3a-3b+2x-\frac{y}{2} & -\frac{1}{2}+6b & \frac{19}{12}-b+\frac{y}{2}-2z\\ 0 & -\frac{2}{3}-a-\frac{x}{2}+\frac{z}{2} & \frac{19}{12}-b+\frac{y}{2}-2z & -3+3z \end{bmatrix}$

K = 
  {{3 - 3 w, -4/3 + a + 2 w, 5/12 + b - w/2, 0},
   {-4/3 + a + 2 w, -1 - 6 a - 3 x, 3/4 + 3 a - 3 b + 2 x - y/2, -2/3 - a - 
      x/2 + z/2},
   {5/12 + b - w/2, 3/4 + 3 a - 3 b + 2 x - y/2, -1/2 + 6 b, 19/12 -b + 
      y/2 - 2 z},
   {0, -2/3 - a - x/2 + z/2, 19/12 - b + y/2 - 2 z, -3 + 3 z}};

It has six unknown variables: $a,b,w,x,y$ and $z$ where $w,x,y,z$ must be positive real numbers. $a$ and $b$ are real numbers.

I need to determine the set of values of the above unknown variables for which the matrix $K$ is positive definite or semi-definite, or show that there are NO values of the unknowns for which the matrix $K$ is positive definite or positive semi-definite.

For the real symmetric matrix $K$:

  • It is positive definite if all its leading principal minors are positive.
  • It is positive semi-definite if all its principal minors are non-negative.

To determine the values for positive definiteness of $K$, I tried:

cond1 = K[[1,1]];
cond2 = Minors[K[[1;;3,1;;3]]][[1,1]];
cond3 = Minors[K][[1,1]];
cond4 = Det[K];
bounds = 
  Simplify[
    Reduce[
      cond1 > 0 && cond2 > 0 && cond3 > 0 && cond4 > 0 && 
        w > 0 && x > 0 && y > 0 && z > 0,
      {a, b, w, x, y, z}, Reals]]

It does not yield any results even after running Mathematica for more than an hour. It would be of great help to me if you could suggest a way of formulating the above problem in a manner such that Mathematica is able to evaluate the values.

$\endgroup$
  • $\begingroup$ well this is a bit silly but Map[#>0&,Eigenvalues[K] // FullSimplify // ToRadicals] $\endgroup$ – chris Mar 28 '15 at 13:21
  • $\begingroup$ The dimensions of your matrix are $3\times 4$ because you omitted a comma. Also, just a warning: You shouldn't use capital letters as variable names. K is a built-in symbol that's reserved for other uses. $\endgroup$ – Jens Mar 28 '15 at 16:41
  • $\begingroup$ @Jens: Thanks for pointing that out. I am new to Mathematica and will keep it in mind. $\endgroup$ – Nick Mar 28 '15 at 18:40
  • $\begingroup$ Probably too slow to be practical, but here is another formulation that avoid roots/radicals. cpol = CharacteristicPolynomial[kmat, t]; Resolve[ForAll[t, And @@ {w > 0, x > 0, y > 0, z > 0}, Implies[cpol == 0, t >= 0]], Reals] $\endgroup$ – Daniel Lichtblau Mar 28 '15 at 19:39
2
$\begingroup$

This seems to work.

kmat = {{3 - 3 w, -4/3 + a + 2 w, 5/12 + b - w/2, 
    0}, {-4/3 + a + 2 w, -1 - 6 a - 3 x, 
    3/4 + 3 a - 3 b + 2 x - y/2, -2/3 - a - x/2 + z/2}, {5/12 + b - 
     w/2, 3/4 + 3 a - 3 b + 2 x - y/2, -1/2 + 6 b, 
    19/12 - b + y/2 - 2 z}, {0, -2/3 - a - x/2 + z/2, 
    19/12 - b + y/2 - 2 z, -3 + 3 z}};
vec = Array[t, Length[kmat]];
prod = Expand[vec.kmat.vec]

(* Out[22]= 3 t[1]^2 - 3 w t[1]^2 - 8/3 t[1] t[2] + 2 a t[1] t[2] + 
 4 w t[1] t[2] - t[2]^2 - 6 a t[2]^2 - 3 x t[2]^2 + 5/6 t[1] t[3] + 
 2 b t[1] t[3] - w t[1] t[3] + 3/2 t[2] t[3] + 6 a t[2] t[3] - 
 6 b t[2] t[3] + 4 x t[2] t[3] - y t[2] t[3] - t[3]^2/2 + 
 6 b t[3]^2 - 4/3 t[2] t[4] - 2 a t[2] t[4] - x t[2] t[4] + 
 z t[2] t[4] + 19/6 t[3] t[4] - 2 b t[3] t[4] + y t[3] t[4] - 
 4 z t[3] t[4] - 3 t[4]^2 + 3 z t[4]^2 *)


Resolve[
 ForAll[Evaluate[vec], And @@ {w > 0, x > 0, y > 0, z > 0}, 
  prod >= 0], Reals]

(* Out[26]= (w <= 1 || x <= 0 || y <= 0 || z <= 0) && (w != 1 || 
   a + 2 w == 4/3 || x <= 0 || y <= 0 || z <= 0) && (w != 1 || 
   x <= 0 || 2 a + x <= -(1/3) || y <= 0 || 
   z <= 0) && (2 b - w == -(5/6) || w != 1 || x <= 0 || y <= 0 || 
   z <= 0) && (w >= 1 || w <= 0 || x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x <= -(43/3) ||
    y <= 0 || z <= 0) && (w >= 1 || w <= 0 || x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x != -(43/3) ||
    y <= 0 || -103 a + 92 b + 12 a b + 45 w + 102 a w - 84 b w - 
     12 w^2 - 72 x + 72 w x + 18 y - 18 w y == 101/3 || 
   z <= 0) && (w >= 1 || w <= 0 || x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x != -(43/3) ||
    y <= 0 || 2 a + x - z == -(4/3) || z <= 0) && (w >= 1 || 
   w <= 0 || -206 b + 12 b^2 - 23 w + 204 b w + 3 w^2 <= -(241/12) || 
   x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x != -(43/3) ||
    y <= 0 || z <= 0) && (w >= 1 || w <= 0 || x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x >= -(43/3) ||
    y <= 0 || -1080 a - 3456 a^2 - 1872 b - 6048 a b - 2592 b^2 - 
     93 w + 1764 a w + 3456 a^2 w + 4248 b w + 5616 a b w + 
     2160 b^2 w + 108 w^2 - 648 a w^2 - 2592 b w^2 - 893 x - 
     4944 a x - 3000 b x + 576 a b x + 432 b^2 x + 1332 w x + 
     4896 a w x + 3312 b w x - 468 w^2 x - 1728 x^2 + 1728 w x^2 + 
     404 y + 1236 a y - 1104 b y - 144 a b y - 540 w y - 1224 a w y + 
     1008 b w y + 144 w^2 y + 864 x y - 864 w x y - 108 y^2 + 
     108 w y^2 >= -6 || z <= 0) && (a >= 0 || w != 1 || x <= 0 || 
   2 a + x != -(1/3) || 6 a - 6 b + 4 x - y == -(3/2) || y <= 0 || 
   z <= 0) && (a >= 0 || w != 1 || x <= 0 || 2 a + x != -(1/3) || 
   y <= 0 || 2 a + x - z == -(4/3) || z <= 0) && (a >= 0 || w != 1 || 
   x <= 0 || 2 a + x >= -(1/3) || y <= 0 || 
   6 a + 36 a^2 + 6 b + 72 a b + 36 b^2 + 6 x + 48 a x + 24 b x + 
     16 x^2 - 3 y - 12 a y + 12 b y - 8 x y + y^2 <= -(1/4) || 
   z <= 0) && (a >= 0 || b >= 1/12 || w != 1 || x <= 0 || 
   2 a + x != -(1/3) || y <= 0 || z <= 0) && (w >= 1 || w <= 0 || 
   x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x >= -(43/3) ||
    y <= 0 || -1080 a - 3456 a^2 - 1872 b - 6048 a b - 2592 b^2 - 
     93 w + 1764 a w + 3456 a^2 w + 4248 b w + 5616 a b w + 
     2160 b^2 w + 108 w^2 - 648 a w^2 - 2592 b w^2 - 893 x - 
     4944 a x - 3000 b x + 576 a b x + 432 b^2 x + 1332 w x + 
     4896 a w x + 3312 b w x - 468 w^2 x - 1728 x^2 + 1728 w x^2 + 
     404 y + 1236 a y - 1104 b y - 144 a b y - 540 w y - 1224 a w y + 
     1008 b w y + 144 w^2 y + 864 x y - 864 w x y - 108 y^2 + 
     108 w y^2 != -6 || z <= 0 || 
   1134 a - 504 a^2 + 24 b - 504 a b - 770 w - 918 a w + 612 a^2 w + 
     264 b w + 504 a b w + 408 w^2 - 72 a w^2 - 288 b w^2 + 637 x - 
     741 a x - 372 b x + 36 a b x - 603 w x + 738 a w x + 396 b w x - 
     36 w^2 x - 216 x^2 + 216 w x^2 + 244 y + 660 a y + 36 a^2 y - 
     372 w y - 612 a w y + 144 w^2 y + 378 x y - 378 w x y - 587 z - 
     1899 a z - 144 a^2 z - 276 b z - 36 a b z + 1065 w z + 
     1710 a w z + 252 b w z - 540 w^2 z - 1080 x z + 1080 w x z - 
     54 y z + 54 w y z == -410) && (w >= 1 || w <= 0 || x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x >= -(43/3) ||
    y <= 0 || -1080 a - 3456 a^2 - 1872 b - 6048 a b - 2592 b^2 - 
     93 w + 1764 a w + 3456 a^2 w + 4248 b w + 5616 a b w + 
     2160 b^2 w + 108 w^2 - 648 a w^2 - 2592 b w^2 - 893 x - 
     4944 a x - 3000 b x + 576 a b x + 432 b^2 x + 1332 w x + 
     4896 a w x + 3312 b w x - 468 w^2 x - 1728 x^2 + 1728 w x^2 + 
     404 y + 1236 a y - 1104 b y - 144 a b y - 540 w y - 1224 a w y + 
     1008 b w y + 144 w^2 y + 864 x y - 864 w x y - 108 y^2 + 
     108 w y^2 <= -6 || z <= 0 || 
   20832 a + 28224 a^2 + 20832 b + 56448 a b + 28224 b^2 - 6848 w - 
     25680 a w - 27072 a^2 w - 42816 b w - 52416 a b w - 
     25344 b^2 w + 3328 w^2 + 6144 a w^2 + 144 a^2 w^2 + 
     24576 b w^2 + 1152 a b w^2 + 2304 b^2 w^2 + 14500 x + 
     41520 a x + 26208 b x - 4032 a b x - 4032 b^2 x - 19000 w x - 
     41160 a w x - 29952 b w x - 2016 a b w x - 1152 b^2 w x + 
     4800 w^2 x + 144 a w^2 x + 576 b w^2 x + 15505 x^2 + 984 b x^2 + 
     144 b^2 x^2 - 15540 w x^2 - 1008 b w x^2 + 36 w^2 x^2 + 256 y - 
     3024 a y - 4032 a^2 y + 12288 b y - 4032 a b y - 1504 w y + 
     4608 a w y + 4896 a^2 w y - 8832 b w y + 5760 a b w y + 
     1536 w^2 y - 576 a w^2 y - 2304 b w^2 y - 3904 x y - 
     5928 a x y - 3840 b x y + 288 a b x y + 4176 w x y + 
     5904 a w x y + 4032 b w x y - 288 w^2 x y - 1728 x^2 y + 
     1728 w x^2 y + 2560 y^2 + 3072 a y^2 + 144 a^2 y^2 - 
     3072 w y^2 - 2880 a w y^2 + 576 w^2 y^2 + 1728 x y^2 - 
     1728 w x y^2 - 11132 z - 42384 a z - 25344 a^2 z - 25248 b z - 
     52416 a b z - 27072 b^2 z + 20840 w z + 43896 a w z + 
     21888 a^2 w z + 44544 b w z + 46368 a b w z + 21888 b^2 w z - 
     10944 w^2 z - 5616 a w^2 z - 22464 b w^2 z - 26110 x z - 
     35616 a x z - 22608 b x z + 5760 a b x z + 4896 b^2 x z + 
     30360 w x z + 35136 a w x z + 25632 b w x z - 4536 w^2 x z - 
     13824 x^2 z + 13824 w x^2 z - 3520 y z - 3816 a y z - 
     1152 a^2 y z - 14592 b y z - 2016 a b y z + 5712 w y z + 
     2448 a w y z + 13248 b w y z - 2592 w^2 y z - 1728 y^2 z + 
     1728 w y^2 z + 8017 z^2 + 25440 a z^2 + 2304 a^2 z^2 + 
     6360 b z^2 + 1152 a b z^2 + 144 b^2 z^2 - 15156 w z^2 - 
     22464 a w z^2 - 5616 b w z^2 + 8100 w^2 z^2 + 13824 x z^2 - 
     13824 w x z^2 + 1728 y z^2 - 1728 w y z^2 >= -3844) && (w >= 1 ||
    w <= 0 || x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x != -(43/3) ||
    y <= 0 || 
   z <= 0 || -3432 a + 1008 b - 2016 a b - 2016 b^2 + 1342 w + 
     3324 a w - 1008 b w + 2448 a b w + 2016 b^2 w - 408 w^2 + 
     72 a w^2 + 288 b w^2 - 2495 x - 744 b x + 144 b^2 x + 2460 w x + 
     720 b w x + 36 w^2 x + 280 y - 1236 a y + 672 b y + 144 a b y - 
     144 w y + 1224 a w y - 576 b w y - 144 w^2 y - 864 x y + 
     864 w x y + 216 y^2 - 216 w y^2 + 1375 z + 4944 a z - 1944 b z - 
     576 a b z - 144 b^2 z - 1884 w z - 4896 a w z + 1584 b w z + 
     540 w^2 z + 3456 x z - 3456 w x z - 864 y z + 864 w y z != 
    958 || -189216 b + 4966272 b^2 - 290304 b^3 + 53605 w + 
     532608 b w - 9812448 b^2 w - 69120 b^3 w + 20736 b^4 w - 
     19104 w^2 - 503280 b w^2 + 4841856 b^2 w^2 + 352512 b^3 w^2 - 
     6876 w^3 + 159840 b w^3 + 5184 b^2 w^3 + 1296 w^4 - 54948 y + 
     598320 b y - 388800 b^2 y + 20736 b^3 y + 117876 w y - 
     1196208 b w y + 741312 b^2 w y - 20736 b^3 w y - 71136 w^2 y + 
     603072 b w^2 y - 352512 b^2 w^2 y + 8208 w^3 y - 5184 b w^3 y - 
     8676 y^2 + 88992 b y^2 - 5184 b^2 y^2 + 18612 w y^2 - 
     177120 b w y^2 + 5184 b^2 w y^2 - 11232 w^2 y^2 + 
     88128 b w^2 y^2 + 1296 w^3 y^2 + 161711 z - 1201776 b z - 
     4624992 b^2 z + 628992 b^3 z - 20736 b^4 z - 338472 w z + 
     2240352 b w z + 9217152 b^2 w z - 622080 b^3 w z + 
     191016 w^2 z - 883008 b w^2 z - 4593024 b^2 w^2 z - 
     12960 w^3 z - 155520 b w^3 z - 1296 w^4 z + 69408 y z - 
     711936 b y z + 41472 b^2 y z - 148896 w y z + 1416960 b w y z - 
     41472 b^2 w y z + 89856 w^2 y z - 705024 b w^2 y z - 
     10368 w^3 y z - 138816 z^2 + 1423872 b z^2 - 82944 b^2 z^2 + 
     297792 w z^2 - 2833920 b w z^2 + 82944 b^2 w z^2 - 
     179712 w^2 z^2 + 1410048 b w^2 z^2 + 20736 w^3 z^2 <= 
    28920) && (w >= 1 || 
   w <= 0 || -206 b + 12 b^2 - 23 w + 204 b w + 3 w^2 != -(241/12) || 
   x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x != -(43/3) ||
    y <= 0 || z <= 0 || 2 b - y + 4 z == 19/6) && (w >= 1 || 
   w <= 0 || -206 b + 12 b^2 - 23 w + 204 b w + 3 w^2 != -(241/12) || 
   x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x != -(43/3) ||
    y <= 0 || z >= 1 || z <= 0) && (w >= 1 || w <= 0 || x <= 0 || 
   46 a + 3 a^2 - 25 w - 42 a w + 12 w^2 + 27 x - 27 w x >= -(43/3) ||
    y <= 0 || -1080 a - 3456 a^2 - 1872 b - 6048 a b - 2592 b^2 - 
     93 w + 1764 a w + 3456 a^2 w + 4248 b w + 5616 a b w + 
     2160 b^2 w + 108 w^2 - 648 a w^2 - 2592 b w^2 - 893 x - 
     4944 a x - 3000 b x + 576 a b x + 432 b^2 x + 1332 w x + 
     4896 a w x + 3312 b w x - 468 w^2 x - 1728 x^2 + 1728 w x^2 + 
     404 y + 1236 a y - 1104 b y - 144 a b y - 540 w y - 1224 a w y + 
     1008 b w y + 144 w^2 y + 864 x y - 864 w x y - 108 y^2 + 
     108 w y^2 != -6 || z <= 0 || 
   504 a - 284 w - 456 a w + 36 a^2 w + 144 w^2 + 300 x - 36 a x - 
     300 w x + 36 a w x - 9 x^2 + 9 w x^2 - 148 z - 516 a z - 
     36 a^2 z + 276 w z + 468 a w z - 144 w^2 z - 306 x z + 
     306 w x z - 9 z^2 + 9 w z^2 >= -156) && (a >= 0 || w != 1 || 
   x <= 0 || 2 a + x >= -(1/3) || y <= 0 || 
   6 a + 36 a^2 + 6 b + 72 a b + 36 b^2 + 6 x + 48 a x + 24 b x + 
     16 x^2 - 3 y - 12 a y + 12 b y - 8 x y + y^2 != -(1/4) || 
   z <= 0 || -162 a + 72 a^2 - 24 b + 72 a b - 73 x + 84 a x + 
     36 b x + 24 x^2 - 20 y - 84 a y - 42 x y + 39 z + 252 a z + 
     36 b z + 120 x z + 6 y z == 26) && (a >= 0 || w != 1 || x <= 0 ||
    2 a + x >= -(1/3) || y <= 0 || 
   6 a + 36 a^2 + 6 b + 72 a b + 36 b^2 + 6 x + 48 a x + 24 b x + 
     16 x^2 - 3 y - 12 a y + 12 b y - 8 x y + y^2 >= -(1/4) || 
   z <= 0 || -828 a - 1296 a^2 - 432 b - 3024 a b - 1728 b^2 - 
     500 x - 1830 a x - 912 b x - 72 a b x - 645 x^2 - 36 b x^2 + 
     8 y + 48 a y + 216 a^2 y - 672 b y + 288 a b y + 156 x y + 
     252 a x y + 144 b x y + 72 x^2 y - 96 y^2 - 144 a y^2 - 
     72 x y^2 + 264 z + 1962 a z + 1080 a^2 z + 720 b z + 
     2808 a b z + 1728 b^2 z + 990 x z + 1584 a x z + 792 b x z + 
     576 x^2 z + 108 y z + 252 a y z + 720 b y z + 72 y^2 z - 
     189 z^2 - 1296 a z^2 - 324 b z^2 - 576 x z^2 - 72 y z^2 <= 
    96) && (a >= 0 || b != 1/12 || w != 1 || x <= 0 || 
   2 a + x != -(1/3) || y <= 0 || z <= 0 || 
   2 b - y + 4 z == 19/6) && (a >= 0 || w != 1 || x <= 0 || 
   2 a + x >= -(1/3) || y <= 0 || 
   6 a + 36 a^2 + 6 b + 72 a b + 36 b^2 + 6 x + 48 a x + 24 b x + 
     16 x^2 - 3 y - 12 a y + 12 b y - 8 x y + y^2 != -(1/4) || 
   z <= 0 || -200 a + 12 a^2 - 100 x + 12 a x + 3 x^2 + 28 z + 
     204 a z + 102 x z + 3 z^2 <= 92/3) && (a >= 0 || b != 1/12 || 
   w != 1 || x <= 0 || 2 a + x != -(1/3) || y <= 0 || z >= 1 || 
   z <= 0) && (a >= 0 || b == 1/12 || w != 1 || x <= 0 || 
   2 a + x != -(1/3) || y <= 0 || z <= 0 || 
   51 a - 18 b + 36 a b + 36 b^2 + 35 x + 12 b x - 5 y + 18 a y - 
     12 b y + 12 x y - 3 y^2 - 15 z - 72 a z + 36 b z - 48 x z + 
     12 y z != -(41/4) || -33 b + 2124 b^2 + 144 b^3 - 19 y + 
     240 b y - 144 b^2 y - 3 y^2 + 36 b y^2 + 58 z - 528 b z - 
     2016 b^2 z + 24 y z - 288 b y z - 48 z^2 + 576 b z^2 <= 145/12) *)

Caveat: I do not know offhand how to do a sanity check on this result. (If I claimed to know, I'd probably need a sanity check on myself.)

$\endgroup$
  • $\begingroup$ Thanks for spending time on this! And @@ {w > 0, x > 0, y > 0, z > 0} in the Resolve command does not seem to enforce the constraint that $w,x,y,z$ must be positive. On the same lines, I tried Resolve[ ForAll[Evaluate[vec], w > 0 && x > 0 && y > 0 && z > 0 && prod >= 0], Reals], which seems to do much better but they all essentially provide the result that has a condition that equals Det[kmat] > 0, which is a non-linear algebraic equation of degree 4 and it is difficult to make sense out of it. $\endgroup$ – Nick Mar 28 '15 at 21:44
  • $\begingroup$ With this approach, the problem seems to boil down to solving non-linear algebraic equations simultaneously. $\endgroup$ – Nick Mar 28 '15 at 22:10
  • $\begingroup$ Over the reals,no less. One can try GenericCylindricalDecomposition[res, {a, b, w, x, y, z}] where res is the result of that Resolve. But that brought my laptop to its knees and I had to kill the kernel. $\endgroup$ – Daniel Lichtblau Mar 29 '15 at 13:59
  • $\begingroup$ Thanks Daniel! One set of values that makes all the elements of the matrix zero and essentially proves semi-definiteness are {w->1,x->1,y->1,z->1,a->-2/3,b->1/12}. I haven't been able to workout anything for definiteness. $\endgroup$ – Nick Mar 31 '15 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.