# Proving positive definiteness or semi-definiteness of a matrix

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.

• well this is a bit silly but Map[#>0&,Eigenvalues[K] // FullSimplify // ToRadicals] – chris Mar 28 '15 at 13:21
• 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. – Jens Mar 28 '15 at 16:41
• @Jens: Thanks for pointing that out. I am new to Mathematica and will keep it in mind. – Nick Mar 28 '15 at 18:40
• 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] – Daniel Lichtblau Mar 28 '15 at 19:39

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= 3 t^2 - 3 w t^2 - 8/3 t t + 2 a t t +
4 w t t - t^2 - 6 a t^2 - 3 x t^2 + 5/6 t t +
2 b t t - w t t + 3/2 t t + 6 a t t -
6 b t t + 4 x t t - y t t - t^2/2 +
6 b t^2 - 4/3 t t - 2 a t t - x t t +
z t t + 19/6 t t - 2 b t t + y t t -
4 z t t - 3 t^2 + 3 z t^2 *)

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

(* Out= (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.)

• 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. – Nick Mar 28 '15 at 21:44
• With this approach, the problem seems to boil down to solving non-linear algebraic equations simultaneously. – Nick Mar 28 '15 at 22:10
• 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. – Daniel Lichtblau Mar 29 '15 at 13:59
• 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. – Nick Mar 31 '15 at 17:46