Checking if a symbolic symmetrical Matrix is negative definite

Question

I have the following problem finding the value ranges for the parameters of a symbolic symmetrical matrix in order to make it negative definite:

The matrix I'm talking about looks as follows

A := {{-1, -b, a, 0}, {-b, -1, 0, 0}, {a, 0, -a, -b a}, {0, 0, -b a, -a}}

and as you can see in matrix form, it is a symmetrical matrix

\begin{array}{cccc} -1 & -b & a & 0 \\ -b & -1 & 0 & 0 \\ a & 0 & -a & -a b \\ 0 & 0 & -a b & -a \\ \end{array}

Now I'm trying to find the value ranges of a and b in order to make the matrix negative definite. It is important that b depends on a and not the other way round, since the matrix is part of an economic model, which doesn't make any sense otherwise.

First I used the approach to find the value ranges, which make all Eigenvalues negative and thus lead to a negative definite matrix

Reduce[Eigenvalues[A] < 0, {a, b}]

which yields

0 < a < 1 && -Sqrt[1 - Sqrt[a]] < b < Sqrt[1 - Sqrt[a]]

Everything fine so far. But then I tried a different approach. If the k-th order leading principal minor of the matrix has sign (-1)^k, then the matrix should be negative definite, so I'm expecting the same result:

A1 := {{-1}}
A2 := {{-1, -b}, {-b, -1}}
A3 := {{-1, -b, a}, {-b, -1, 0}, {a, 0, -a}} 

Reduce[{Det[A1] < 0, Det[A2] > 0, Det[A3] < 0, Det[A] > 0}, {a, b}]

which yields

0 < a < 1 && Root[1 - a - 2 #1^2 + #1^4 &, 2] < b < Root[1 - a - 2 #1^2 + #1^4 &, 3]

which is in radicals

ToRadicals[
0 < a < 1 && Root[1 - a - 2 #1^2 + #1^4 &, 2] < b < Root[1 - a - 2 #1^2 + #1^4 &, 3]]

0 < a < 1 && -Sqrt[1 - Sqrt[a]] < b < Sqrt[1 + Sqrt[a]]

As you can see, the result is different than in the first approach (to be more specific the upper bound of b is different), which makes no sense, since both approaches should yield the same result.

Does anyone know what I am doing wrong or which of the results is correct?

Thanks a lot,

Phil

Answer 1

Both of your approaches yield the same answer. it is the application of ToRadicals that causes the answer to be different. First, compare the two limits before the application of ToRadicals:

upperLimit1 = Sqrt[1 - Sqrt[a]];
upperLimit2 = Root[1 - a - 2 #1^2 + #1^4 &, 3];

Plot[upperLimit1, {a, 0, 1}]
Plot[upperLimit2, {a, 0, 1}]

upperLimit1 and upperLimit2 are the same over the region 0 < a < 1. Converting the Root object into radicals is problematic because the Root ordering depends on the parameter a. One suggestion would be to not use ToRadicals and just work with the Root objects. If you really want radicals, a naive application of ToRadicals:

ToRadicals[upperLimit2]

Sqrt[1 + Sqrt[a]]

is only correct for some values of the parameter a. However, in your case, you know something about the parameter a, so you should make use of that by giving ToRadicals an assumption:

ToRadicals[upperLimit2, Assumptions -> 0 < a < 1]

Sqrt[1 - Sqrt[a]]

Note that using:

ToRadicals[0 < a < 1 && upperLimit2]

0 < a < 1 && Sqrt[1 + Sqrt[a]]

does not cause ToRadicals to use 0 < a < 1 as an assumption. The assumption needs to be given explicitly as an option to ToRadicals.

Answer 2

In this answer I will briefly go through the method of using the leading principal minors to derive negative definiteness. Hope this helps you verify your results

A matrix is negative definite when ALL its leading principal minors alternate in sign, with the k-th order leading principal minor having the same sign as $(-1)^k$.

Please note, I am NOT talking about a problem instance with constraints ie I am not talking about bordered matrices. In that case, the rules are a bit different, but this is not the case here.

Also, note, that the order of a minor is derived from the number of columns and rows one has to delete in order to obtain the corresponding submatrix.

Counting is straightforward: For an $nxn$ matrix the k-th order leading principal minor is produced by deleting the last $n-k$ rows and columns of the original matrix. In this fashion, the 1-st order leading principal minor of a $4x4$ matrix is produced after deleting the last $4-1=3$ rows and columns while the 2-nd order leading principal minor of the same matrix needs to have the last $4-2=2$ rows and columns deleted etc.

Finally, note that taking the n-th order leading principal minor of an $nxn$ matrix means deleting $n-n=0$ rows and columns ie the n-th order minor is the determinant of the matrix itself.

Mathematica has (arguably) a lot of ways to produce the leading principal submatrices that are needed to produce the minors (their determinants). One simple and fast way to do it, is:

LeadingPrincipalMinors=Array[Minors[A, #][[1, 1]] &, 4]

Now, checking to verify if the signs of the minors are in agreement with the sign rule we can do the following:

Reduce[
  And @@ MapIndexed[(
    Reduce[#1 (-1)^First[#2] > 0, b[a], Reals]
) &, LeadingPrincipalMinors], b[a], Reals]

The 'trick' I use in this piece of code is to take advantage of the fact that, when two numbers have the same sign, their product is positive. This is what the following excerpt of code from above, does:

#1 (-1)^First[#2] >= 0

Please, note that I have used b[a] instead of b in order to make explicit the dependence of b on a. If you chose to do so, you have to replace the definition of matrix A with something like

A=A/.b->b[a] 

but that is not necessary. I just find it useful to have dependence relationships be defined as explicitly as possible in my code.

Therefore the range of values over which the initial matrix is negative definite depends on a and b[a] being in an appropriate range of values.

Hope that helps :)

-- update --

executing

Reduce[
  And @@ MapIndexed[(
    Reduce[#1 (-1)^First[#2] > 0, b[a], Reals]
) &, LeadingPrincipalMinors], b[a], Reals]//ToRadicals

and

Reduce[And @@ Thread[Eigenvalues[A] < 0], b[a], Reals]

yields the same output, namely:

0 < a < 1 && -Sqrt[1 - Sqrt[a]] < b[a] < Sqrt[1 - Sqrt[a]]

Answer 3

As a way of confirming the OP's results, we can also use the $\mathbf L\mathbf D\mathbf L^\top$ decomposition (as implemented here) to check for negative-definiteness. In particular, we would need to look at the conditions such that all the entries of the diagonal matrix $\mathbf D$ are negative. Thus:

Reduce[Last[LDLT[{{-1, -b, a, 0}, {-b, -1, 0, 0}, {a, 0, -a, -b a}, {0, 0, -b a, -a}}]]
       < 0, {a, b}, Reals]
   0 < a < 1 && 
   Root[1 - a - 2 #1^2 + #1^4 &, 2] < b < Root[1 - a - 2 #1^2 + #1^4 &, 3]

which is identical to the result obtained from checking the minors.