# Prove order N symmetric matrix is negative definite, and the second order derivative of matrix

I have three questions to ask, hope to get some help from you (1) Is there any effective way to determine the negative definiteness of a N-order matrix $\textbf{M}$? I think it's impossible to solve it by using the order principal minor determinant or eigenvalue method of $-\textbf{M}$, so how can I prove it? thx! $\textbf{M}$ is a symmetric matrix.

(2) If $\frac{\partial \mathcal{F}}{\partial B} = {A^{\dagger}} \left( \Omega+ A B A^{\dagger} \right)^{-1} A\\$ ($A, B, \Omega$ are all N-order matrices), Then how to calculate the second derivative of B $\frac{\partial^2 \mathcal{F}}{\partial B^2}$? Should it be $\frac{\partial^2 \mathcal{F}}{\partial B^2} = {A^{\dagger}}{A^{\dagger}} \left( \Omega+ A B A^{\dagger} \right)^{-2} AA\\$ or according to $\frac{d}{dx}A^{-1}=-A^{-1}\frac{dA}{dx}A^{-1}$, we can get $\frac{\partial^2 \mathcal{F}}{\partial B^2} = -{A^{\dagger}}{A^{\dagger}}\left( \Omega+ A B A^{\dagger} \right)^{-1} \left( \Omega+ A B A^{\dagger} \right)^{-1} AA\\$? Or there is any other way to solve it? thx!

(3) Game theory question: How to present the best response mapping of a two-player pure strategic game? I mean, if the payoff function $x_1^* = \arg \max_{x_1} u_1(x_1,x_2)=\log(\frac{1}{1+x_1+x_2})-\lambda_1 x_1$ and from symmetrics we can get the $\arg \max_{x_2} u_2(x_2,x_1)=\log(\frac{1}{1+x_1+x_2})-\lambda_2 x_2$ are all concave functions, but we know that depending on the value range of $x$ and $\alpha$, we may have 3 cases for the maximum of $u_1, u_2$, then how can we write down the best response mapping? Are best response mapping and best response function the same definitions?

Thank you very much for your help!

It is better to send $3$ different posts.
1. You want $M<0$, that is $-M>0$. You can calculate the $N$ $\det$ of the principal minors of $-M$; numerically the complexity is in $O(N^4)$. There is a better method: apply to $-M$ the Choleski algorithm; if it works, then $-M>0$, otherwise it is not. Moreover the complexity of this algorithm is in $O(N^3)$.
2. To calculate $\frac{\partial^ 2 \mathcal{F}}{\partial B^2}$ is not difficult if your $\frac{\partial \mathcal{F}}{\partial B}$ is correct. Indeed, I do not understand how you found this first derivative; in any case, $\mathcal{F}$ is certainly not a $\log$ function.
Answer to (2): In general derivative of a matrix valued function by a matrix will give a 4-dimensional array. We have $\partial(a^{-1})_{ij}/\partial a_{kl}=-(a^{-1})_{ik}(a^{-1})_{lj}$. We this, chain and product rule it should be poosible to compute the derivative. However it requires some lengthy computations.
• Thanks for your answer! But i think this is just the definition of derivative of matrix. e.g. $F(X) = (f_{ij}(X))_{s \times t}, X = (x_{ij})_{m \times n}$, then $\frac{dF}{dX} \in C^{ms \times nt}$, which is a super matrix right? but I wondered if there is any theorem or formula so I can calculate more easily, since it's matrix valued function, we can treat the matrix element as a whole and do not pay much attention to the entries inside? thx! and is there anybody who has any idea about the other two questions? thx! – Jie Tian Apr 8 '15 at 18:55