How to show the following matrix is positive definite. \begin{equation} \sum_{i=1}^n \Big[(d_i^Tp)^2\left\{\left( \begin{array}{c} d_i\\ A_ip \end{array} \right) \left( \begin{array}{c} d_i\\ A_ip \end{array} \right)^T - (d_i^Tp) \left( \begin{array}{cc} 0 & A_i^T\\ A_i&0 \end{array} \right) \right\}\Big], \end{equation} where $A_i$ is a $k\times m$ matrix which has at least non-zero element in one row or column and at most one non-zero element in other rows, $p$ and $d_i$ are $m\times 1$ vectors with $p_j \in (0,1)$ for all $j=1,\ldots,m$, $p^T{\bf 1}=1$ and only one non-zero element in $d_i$.

  • $\begingroup$ I couldn't show positive definiteness of each term in that summation. One may be able to write the above as a quadratic form and then can say it is positive definite. $\endgroup$ – Sedi May 22 '15 at 14:03
  • $\begingroup$ I guess the right way to do it is induction because if n grows it becomes very difficult to handle. $\endgroup$ – Piquito May 22 '15 at 14:42
  • $\begingroup$ in fact the things which I tried was the probability of this to be positive definite is going to 1 when $n$ is large enough. $\endgroup$ – Sedi May 22 '15 at 16:59
  • $\begingroup$ Dear Luis, as I mentioned in my first comment, it won't be true for n=1 always $\endgroup$ – Sedi May 23 '15 at 13:24
  • $\begingroup$ I write the above as: $$ \left( \begin{array}{c} J^T\\ {\bf 0} \end{array} \right) \left( \begin{array}{c} J\\ {\bf 0} \end{array} \right)^T+\left( \begin{array}{c} {\bf 0}\\ Z^T \end{array} \right) \left( \begin{array}{c} {\bf 0}\\ Z \end{array} \right)^T-\left( \begin{array}{c} J^TD_1\\ Z^TD2 \end{array} \right)\left( \begin{array}{c} D_1^TJ\\ D_2^TZ \end{array} \right)^T+\left( \begin{array}{c} J^TB^T\\ Z^Tp^T \end{array} \right)\left( \begin{array}{c} BJ\\ pZ \end{array} \right)^T, $$ when $D_1D_1^T=I$ and $D_2D_2^T=I$. $\endgroup$ – Sedi May 25 '15 at 12:40

You cannot, because it is not always positive definite. Counterexample: with $n=1$ (i.e. there is only one summand), $d_1=\pmatrix{1\\ 1},\,p=\frac12d_1$ and $A_1=\pmatrix{2&1\\ 1&1}$, the resulting matrix in the pair of the curly braces is $$ B_1=\pmatrix{1&1&-\frac12&0\\ 1&1&\frac12&0\\ -\frac12&\frac12&\frac94&\frac32\\ 0&0&\frac32&1}. $$ $B_1$ is real symmetric, but when $x=(1,-1,1,-1)^T$, we have $x^TB_1x=-\frac74<0$. Hence $B_1$ is not even positive semidefinite.

By perturbing $A_1$ by a little, we can also get an infinity family of distinct matrices $B_1,\,B_2,\,\ldots$ such that for the aforementioned vector $x$, each $x^TB_ix$ is negative. Hence we can obtain a counterexample for an arbitrary $n$.

  • $\begingroup$ You are correct, but $A_i$ in my problem is in such a way that there is atleast one non-zero element in each row or columns. Thank you for reminding me to edit the question. $\endgroup$ – Sedi May 23 '15 at 10:03
  • $\begingroup$ Moreover I mentioned that it is not possible to show for each term and your example is when n=1 $\endgroup$ – Sedi May 23 '15 at 13:23
  • $\begingroup$ @Sedi Nothing changes even if $n\ne 1$ and each $A_i$ is entrywise nonzero. See my new edit. $\endgroup$ – user1551 May 24 '15 at 0:46
  • $\begingroup$ Dear user1551, Thank you for the answer, Ur answer for earlier question is correct. But I realized in my case $d_i$ vector has only one non-zero element and $n$ goes to infinity. $\endgroup$ – Sedi May 25 '15 at 12:14
  • $\begingroup$ Dear user1551, I am trying to write it as quadratic form, as I have mentioned above, but I have one negative sign. $\endgroup$ – Sedi May 25 '15 at 12:43

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.