3
$\begingroup$

A necessary condition in any quadratic programming to be convex is the matrix $\mathbf{Q}$ in the formulation $x^\intercal \mathbf{Q}x$ to be positive definite or positive semidefinite. Positive definiteness (PD) or semidefiniteness (PSD) requires the eigen values of the matrix either to be $> 0$ or $\geq 0$ respectively. Is the symmetry of the matrix $\mathbf{Q}$ a necessary condition for the matrix to be PD or PSD?

This link in Matlab documentations checks for the symmetry of the matrix before finding the eigen values. I can't find this information explicitly anywhere in any reference.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

Yes, a real PSD matrix $M$ is a symmetric matrix with $$x^TMx\ge 0$$ for any $x$ (see e.g. https://en.wikipedia.org/wiki/Definite_matrix).

However, this is not a real restriction. (We have two meanings of "real" here). We can form $$M' = \frac{M+M^T}{2}$$ Now $M'$ is symmetric and we have $$x^TM'x = x^TMx$$ for any $x$. So you can make $M$ symmetric by preprocessing it without affecting the solution.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks sir for this detailed answer. Consider this matrix: \begin{equation} \mathbf{Q} = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{bmatrix} \end{equation} Now if I apply the equation you kindly provided, the eigen values I get are (-0.5000, -0.5000, 0.5000, 0.5000) which turns the matrix to be indefinite, am I right? $\endgroup$
    – Ibrahim Amer
    Commented Jun 27, 2021 at 18:56
  • 2
    $\begingroup$ Yes, the "symmetrized" matrix is indefinite. $\endgroup$
    – prubin ♦
    Commented Jun 27, 2021 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.