# PD matrix perturbation

I ran into the following problem in my research:

Given an invertible matrix $A \in \mathbb{C}^{n\times n}$, and define $B = A^{-1}$. Denote the $i$th standard basis in $\mathbb{R}^n$ by $e_i$ and the $i$th row of $B$ by $B_{i\bullet}$. Then is the following true \begin{equation} \label{1} \alpha A^HA - e_ie_i^T \succeq 0, \end{equation} when $\alpha \geq \|B_{i\bullet}\|_2^2$?

Numerical results seem to suggest that it always holds but I've not been able to find a proof.

• What does the notation 'larger than 0' mean? Mar 15 '17 at 18:56
• @Student It means the matrix on the LHS is positive semi-definite.
– Ted
Mar 15 '17 at 19:06
• I think you are correct. I made some computations, but I need to double check them. I will try to post an answer tomorrow. One last question: the norm you used in the inequality with $\alpha$ is the regular Euclidean norm raised to power 2, right? Mar 15 '17 at 19:17
• @Student, that's right, it is the Euclidean norm. Thank you for your help!
– Ted
Mar 15 '17 at 19:19

What I thought is the following: let $z$ be a complex nonzero columnvector, then we want to show that $$z^H(\alpha A^HA - e_ie_i^T)z \geq 0.$$ This is equal with showing that $$\alpha (Az)^H(Az) - z^He_ie_i^Tz \geq 0.$$ We have that the $2$-norm $\|x\|_2^2 = \langle x, x \rangle$, where $\langle \cdot, \cdot \rangle$ denotes the inner product of vectors. Moreover, you can compute yourself that $z^He_ie_i^Tz = |z_i|^2$, where $z_i$ is the $i$th entry of the vector $z$.

Let us now focus on the term $\alpha(Az)^H(Az)$ for which we have the following inequality: $$\alpha(Az)^H(Az) \geq \|B_{i\bullet}\|_2^2 \|Az\|_2^2$$ because of the definition of $\alpha$. Let us now use the inequality of Cauchy-Schwarz, which states that for every $p$-norm we have that $|x^Hy| \leq \|x\|_p\|y\|_p$. Applying this for $p = 2$ and the fact that $f: \mathbb{R} \to \mathbb{R}: x \mapsto x^2$ is a strictly increasing function on $\mathbb{R}^+$, we have that $$\|B_{i\bullet}^H\|_2^2 \|Az\|_2^2 \geq |B_{i\bullet} Az|^2$$ (we can write $\|B_{i\bullet}^H\|_2^2 = \|B_{i\bullet}\|_2^2$ for a vector).

If we now note that $Az$ is a linear combination of the columns of $A$ with coefficients $z_j$ (the entries of the vector $z$) and we also have that $B_{i\bullet}a_j = \delta_{i,j}$ where $a_i$ denotes the $i$th column of the matrix $A$, we have that $$|B_{i\bullet} Az|^2 = |B_{i\bullet}a_iz_i|^2 = |z_i|^2.$$

As a result, we find that $$\alpha (Az)^H(Az) - z^He_ie_i^Tz \geq 0 \geq |z_i|^2 - |z_i|^2 = 0,$$ which concludes this proof.

$\textbf{Remark:}$ Any thoughts on this proof are welcome, since I am not completely sure about the step where I say that the linear combination only has a term in $z_i$ since the other terms would vanish.

• Thank you very much, it looks great! $B_{i\bullet}A$ is indeed equal to $e_i^T$ since $BA = I$ by definition.
– Ted
Mar 16 '17 at 3:27
• @Ted if this is for research, perhaps you still should let someone else check it,just in case... Mar 16 '17 at 9:46
• sure, I will let someone check it. Thanks!
– Ted
Mar 16 '17 at 16:07
• @Ted since It started to doubt my proof, I have asked on this site of someone could check my proof and the person who did also said it looked fine. (I forgot that $A^HA$ is positive semi-definite itself, so it appeared counter intuitive to me that you could correct it with such minimal effort). So right now, I am quite sure that this proof is quite correct :) Mar 16 '17 at 16:11