# Verify positive definiteness using random numbers

I wish to verify whether T'T - IdentityMatrix is always positive definite for a certain choice of elements of T'T.

T'T = {{t11^2, t11*t12},{t11*t12, t12^2+t22^2}};


Now, I have written the following program to check my assumptions on t11 etc which are: t11^2 > 1 t22^2 > 1 and t12 completely free.

co = 0;
Do[{t11s = RandomReal[{1, 10^12}],
If[RandomReal[{0, 1}] >= 0.5, t11 = Sqrt[t11s], t11 = -Sqrt[t11s]],
t22s = RandomReal[{1, 10^12}],
If[RandomReal[{0, 1}] >= 0.5, t22 = Sqrt[t22s], t22 = -Sqrt[t22s]],
t12 = RandomReal[{-10^12, 10^12}],
ttm = {{t11s, t11*t12}, {t11*t12, t12^2 + t22s}},
If[Transpose[ve].(ttm-IdentityMatrix).ve > 0, co++]}, {10^5}]
co


However, my program, based on random draws, generates odd results. For fixed ve as well as for random draws.

Thank you so much!

• Note that T'T is a syntax error. Variable names cannot contain the ' character. – DumpsterDoofus Sep 23 '14 at 1:06
• Oh, that was just for notational convenience here on Stackexchange but thanks for pointing it out! – Hirek Sep 23 '14 at 10:41

The eigenvalues are

Eigenvalues[{{t11^2, t11*t12}, {t11*t12, t12^2 + t22^2}} - IdentityMatrix]


giving

{1/2 (-2 + t11^2 + t12^2 + t22^2 - Sqrt[ t11^4 + 2 t11^2 t12^2 + t12^4 - 2 t11^2 t22^2 + 2 t12^2 t22^2 + t22^4]), 1/2 (-2 + t11^2 + t12^2 + t22^2 + Sqrt[ t11^4 + 2 t11^2 t12^2 + t12^4 - 2 t11^2 t22^2 + 2 t12^2 t22^2 + t22^4])}

Assuming that the radicand is real-valued, one then notes that positive-definiteness is equivalent to

(-2 + t11^2 + t12^2 + t22^2)^2 >
t11^4 + 2 t11^2 t12^2 + t12^4 - 2 t11^2 t22^2 + 2 t12^2 t22^2 + t22^4


which simplifies to

$$1 + t11^2 (-1 + t22^2) > t12^2 + t22^2$$

which can be false when t12 becomes arbitrarily large. Thus the matrix is not always positive definite; Daniel Lichtblau's answer shows a way to construct explicit counterexamples.

• Nice one - the low tech way! But for larger, less tractable issues, would you know of a good way to test this with random numbers (which is then only a probabilistic statement)? – Hirek Sep 23 '14 at 10:46
• @Hirek: Sure, but when you say larger, that means larger than $2\times 2$, right? What are the conditions on the matrix elements? Is the restriction that the on-diagonal elements $t_{ii}^2>1$ and no restrictions on the off-diagonal elements? And are we computing the eigenvalues of $T^\dagger T-I$, where $I$ is the identity matrix? If that's what you're looking for, I can give an example method. – DumpsterDoofus Sep 23 '14 at 14:42
• Yes, precisely what you said @DumpsterDoofus T'T - I and those restrictions! Thank you so much! The thing is with positive definiteness it is sometimes hard to verify analytically. In many applications however being say 99% sure that something is or isnt pd is actually good and I thoiught random numbers are a great way to at least obtain a guess. – Hirek Sep 23 '14 at 15:12
• @Hirek: One other question: I just realized that the matrix that you give is not of the form $T^\dagger T$, but rather is of the form $T^\dagger .* T$, where $.*$ is the elementwise product, not the matrix product. Is this what you intended? I ask because typically in linear algebra, juxtaposition of two matrices is almost always meant to be the product of the matrices, not the elementwise product of the matrices. – DumpsterDoofus Sep 23 '14 at 15:23
• @Hirek: Oops, actually now that I look at it a third time, I have no idea what you are trying to do, as the (2,2) entry is not of the form that an elementwise product would give. What exactly is T'T supposed to be? It's not clear based on the example you give, but it's not $T^\dagger T$. Or was the T'T that you gave a typo? In linear algebra, the product of two matrices is a matrix whose elements are the dot products of the rows of the first matrix and the columns of the second matrix, so you might want to check your math to make sure you're typing in the matrix correctly. – DumpsterDoofus Sep 23 '14 at 15:26

Could look for a counterexample using FindInstance.

tmat = {{t11^2, t11*t12}, {t11*t12, t12^2 + t22^2}} -
IdentityMatrix;
evals = Eigenvalues[tmat];

FindInstance[(evals[] <= 0 || evals[] <= 0) &&
t11^2 >= 1 && t22^2 >= 1, Variables[tmat], Reals]

(* Out= {{t11 -> Sqrt, t12 -> 1, t22 -> Sqrt[3/2]}} *)


To get conditions on positive definiteness one could use Reduce with a setup similar to that above.

• Thanks for your suggestion, however you use || which means or right? Shouldn't it be && for a negative definite matrix have both eigenvalues negative? – Hirek Sep 27 '14 at 16:53
• Yes, I use Or, in order to get a counterexample. If either eigenvalue is nonpositive then the matrix is not positive definite. If either is strictly negative then it is not positive semidefinite. It need not be negative (semi)definite in order to not be pos def. – Daniel Lichtblau Sep 27 '14 at 18:00