3
$\begingroup$

Given a non-invertible, diagonalizable matrix $A$, I wish to transform it into another matrix $B$ that satisfies:

  • $B$ is invertible
  • all non-zero eigenvalues of $A$, are also eigenvalues of $B$
  • all of the eigenvectors correspond to non-zero eigenvalues of $A$, are also eigenvectors that correspond to the same eigenvalues of $B$

There are no other constraints on $B$.

What is the simplest way to calculate such a matrix $B$? (of course, there are infinitely many such matrices, but I want an easy way to calculate some such a matrix $B$).

Thanks in advance!

$\endgroup$
  • 2
    $\begingroup$ Add the projector onto $\mathop{\rm Ker} A$ along $\mathop{\rm Im} A$... $\endgroup$ – Ilya Bogdanov Oct 1 '16 at 18:58
  • 3
    $\begingroup$ Let $f(T)$ be the characteristic polynomial of $A$ with all the factors of $T$ divided out, and take $B=A+f(A)$. $\endgroup$ – Julian Rosen Oct 1 '16 at 19:35
  • $\begingroup$ Ilya: the matrix $A$ is not necessarily orthogonally diagonalizable. Consider, e.g., $A = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$, which is perfectly diagonalizable with null space in the anti-diagonal direction; Yet, you can check that $B = A + \text{Proj}_{N(A)}$ no longer has the eigenvector $(1,0)^T$ of $A$, since $(1,0)^T$ has a component in the anti-diagonal direction. $\endgroup$ – Nawaf Bou-Rabee Oct 1 '16 at 20:13
  • 1
    $\begingroup$ @Nawai: My projector is not orthogonal: it is along $\mathop{\rm Im} A$, so all the vectors in the image are mapped to zero. $\endgroup$ – Ilya Bogdanov Oct 2 '16 at 8:13
  • 1
    $\begingroup$ @NawafBou-Rabee: the projector is $\left[\begin{matrix}0& -1\\0& 1\end{matrix}\right]$: it maps $(1,0)^T$ to $0$, but $(1,-1)^T$ to itself. The result is thus $\left[\begin{matrix}1& 0\\0& 1\end{matrix}\right]$. $\endgroup$ – Ilya Bogdanov Oct 4 '16 at 14:58
3
$\begingroup$

Here we expand a bit on Ilya Bogdanov's answer: $B = A + \Pi$, where $\Pi$ is the oblique projection matrix onto the null space of $A$ along the column space of $A$.

Oblique Projection Matrix

Given an $n \times n$ matrix $A$ with rank $r$. Compute its leading $r$ left singular vectors $\{ \vec{u}_i \in \mathbb{R}^n \mid 1 \le i \le r \}$. The oblique projection matrix onto the null space of $A$ or $\text{Null}(A)$ along the column space of $A$ or $\text{Col}(A)$ is: $$ \Pi = I_n - \sum_{1 \le i \le r} \vec{u}_i \vec{u}_i^T \;. \tag{$\star$} $$

Computational Cost of Constructing Oblique Projection Matrix

Note that computing this projection matrix only requires computing a compact SVD, i.e., finding the positive eigenvalues $\{ \lambda_i \}$ of $A^T A$ and their associated eigenvectors $\{ \vec{v}_i \}$. Then set $$ \vec{u}_i = \frac{1}{\sqrt{\lambda_i}} A \vec{v}_i \tag{$\diamond$} $$ for $1 \le i \le r$.

Why does ($\star$) work?

Recall that the left singular vectors are an orthonormal basis for $\text{Col}(A)$. Thus, one can always write the projection as: $$ \Pi \vec{x} = \vec{x} -\sum_{1 \le i \le r} \alpha_i (\vec{u}_i \bullet \vec{x}) \vec{u}_i $$ where the scalars $\{ \alpha_i \}$ are determined such that $\Pi \vec{x} \in \text{Null}(A) = \text{Null}(A^TA)$. In particular, $$ (A A^T \vec{u}_j) \bullet ( \vec{x} - \sum_{1 \le i \le r} \alpha_i \vec{u}_i ) = 0 \implies \alpha_i = \vec{u}_i \bullet \vec{x} \quad \text{for $1 \le i \le r$} $$ which gives the oblique projection map in ($\star$).

Transformed Matrix

Ilya proposed to the transform $B=A + \Pi$. This works because if $\vec{x}$ is an eigenvector of $A$ with nonzero eigenvalue then clearly $\vec{x} \in \text{Col}(A)$ and $$ B \vec{x} = A \vec{x} = \lambda \vec{x} $$ On the other hand, if $\vec{x}$ is an eigenvector of $A$ associated with a zero eigenvalue then $\vec{x} \in \text{Null}(A)$ or $\vec{x} \perp \text{Col}(A^T)$, and hence from ($\diamond$), $$ B \vec{x} = \vec{x} $$ So, $B$ fulfills the OP's desiderata.

MATLAB Implementation

One can replace $A$ below with any diagonalizable matrix.

% construction

A = [1 1 1; -2 -2 -1; 0 0 -1];
[n,n]=size(A);
r=rank(A);
[U,S,V]=svds(A,r);
B=A+(eye(n)-U*U');

% verification

[vectorsA,valuesA]=eig(A);
[vectorsB,valuesB]=eig(B);

valuesA=diag(valuesA);
ix=~(valuesA==0);
valuesA=valuesA(ix);
vectorsA=vectorsA(:,ix);

for i=1:length(valuesA)
  B*vectorsA(:,i)-valuesA(i)*vectorsA(:,i)
end
$\endgroup$

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.