1
$\begingroup$

Let A be positive definite and not symmetric (edit: and real).

Why is $I - \alpha A$ a contraction for sufficiently small $\alpha$?


I see why this is the case if A is symmetric since it will have an eigendecomposition and give:

$Q(I - \alpha \Lambda)Q^T$

Where $\Lambda$ is diagonal with positive eigenvalues on the diagonal. But what can be said if A if not symmetric? Is it valid to use a singular value decomposition instead and say that the singular values must be positive and somehow argue that way?


The question comes from reading Reinforcement Learning by Sutton & Barto and the boxed text Proof of Convergence of Linear TD(0) and also Reinforcement Learning: Algorithms and Convergence by Heitzinger (Theorem 6.1).

$\endgroup$
11
  • $\begingroup$ define what a "positive definite" not symmetric matrix is, please $\endgroup$
    – Exodd
    Aug 18, 2021 at 10:05
  • $\begingroup$ It's a wild guess, but probably a matrix $A$, such that $x^TAx>0$ for all $x\neq 0$. But maybe i am false. $\endgroup$
    – Jochen
    Aug 18, 2021 at 10:13
  • $\begingroup$ Yes "Confusingly, the discussion of positive definite matrices is often restricted to only Hermitian matrices, or symmetric matrices in the case of real matrices". mathworld.wolfram.com/PositiveDefiniteMatrix.html $\endgroup$ Aug 18, 2021 at 10:16
  • $\begingroup$ The result is false. Consider $\mathbb{R}^2$ with the $\infty$-norm and $A=\begin{pmatrix}1-\epsilon&1\\0&1-\epsilon\end{pmatrix}$, for example. $\endgroup$ Aug 18, 2021 at 12:49
  • $\begingroup$ $(I-\alpha A)(1,-1)=(1+\alpha\epsilon,-(1-\alpha(1-\epsilon)))$ so $\lVert(1-\alpha A)(1,-1)\rVert_\infty=1+\alpha\epsilon>1=\lVert(1,-1)\rVert_\infty$ for all $\alpha>0$. $\endgroup$ Aug 18, 2021 at 15:00

1 Answer 1

2
$\begingroup$

The eigenvalues of $I-\alpha A$ are in the form $1-\alpha\lambda$ for $\lambda\in\Lambda(A)$. From the definition of positive definite matrix, $Re(\lambda)>0$ and $$ |1-\alpha\lambda|^2 = (1-\alpha Re(\lambda))^2 + \alpha^2Im(\lambda)^2 = 1 - 2\alpha Re(\lambda) + \alpha^2|\lambda|^2 $$ that is less than 1 whenever $$\alpha < 2 Re(\lambda)/|\lambda|^2$$ so you just need to impose $$ \alpha < 2 \inf_\lambda Re(\lambda)/|\lambda|^2. $$ Notice that $Re(\lambda)/|\lambda|^2$ is always positive thanks to $Re(\lambda)>0$.

$\endgroup$
3
  • $\begingroup$ Thanks but as I understand it, the existence of an eigendecomposition is only guaranteed if the positive definite matrix is symmetric. I've also edited the question to make clear that the matrix of interest is real if that helps. $\endgroup$ Aug 18, 2021 at 10:48
  • $\begingroup$ OK I've now read and understood that all square matrices are guaranteed to have complex eigenvalues and eigenvectors. $\endgroup$ Aug 18, 2021 at 12:06
  • $\begingroup$ @RobinCarter Indeed. In fact you can define a contraction just by requiring that all eigenvalues have norm less than 1 $\endgroup$
    – Exodd
    Aug 18, 2021 at 13:29

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.