4
$\begingroup$

This question is a generalisation of Eigenvalues of $AB$ and $BA$ where $A$ and $B$ are rectangular matrices which itself is a generalisation of Eigenvalues of $AB$ and $BA$ where $A$ and $B$ are square matrices.

Let $A$ be an $m \times n$ matrix and B and $n \times k$ matrix. Obviously, the matrix product $AB$ is possible, whereas the product $BA$ is not. Assume $n<k<m$, such that $AB$ is a large matrix.

Is there anything we can do to either matrix $A$ or $B$, such that the product $BA$ becomes possible and such that the eigenvalues of $BA$ say something about the eigenvalues of the original $AB$?

I am thinking of procedures such as:

  • Truncating $A$ (making it $k \times n$)
  • Appending some values to $B$ (making it $n \times m$)
  • Interpolating values in $B$
  • Taking random samples
  • etc.

Motivation 1 (theoretical): The matrix $AB$ is large and clearly degenerate. Therefore, there must be a smaller matrix which captures the same information as $AB$ (i.e. has the same eigenvalues). If $k=m$, then $BA$ would be such a smaller matrix, as discussed in Eigenvalues of $AB$ and $BA$ where $A$ and $B$ are rectangular matrices.

Motivation 2 (practical): The eigendecomposition of a very large matrix is computationally expensive and may require special hardware. If the problem can be simplified, e.g. by decomposing the smaller $BA$, then the analysis can be performed more efficiently.

Alternatively, is there anything we can say about the eigenvalues of $AB$ without performing the product, i.e. based on analyses of $A$ and $B$ separately.

$\endgroup$
  • 1
    $\begingroup$ Is $A'$ the transpose of $A$? If yes, and if $AB$ is defined, then $B'A'$ is defined and $(AB)' = B'A'$. By referring to the eigenvalues of $AB$ you are implying that $AB$ is square. This clashes with your assumption $k<m$. What is possible and useful in practice is to compute the SVD of the product $AB$. This can be done quickly. Are you interested in that procedure? $\endgroup$ – Carl Christian Sep 27 '17 at 17:53
  • $\begingroup$ @CarlChristian With $A'$ I do not mean the transpose of $A$, but some matrix very similar to $A$ which can be post-multiplied with $B$ (or some $B'$, similar to $B$). How you define 'similar' is precisely my question. Update: I removed the primes from my question to avoid futher confusion. $\endgroup$ – LBogaardt Sep 27 '17 at 19:40
  • $\begingroup$ Yes, I'm starting to see that the generalisation from eigenvalue to singular values is not trivial. If anyone can help me understand the difference in this context, that too would be helpful. $\endgroup$ – LBogaardt Sep 27 '17 at 19:41
  • $\begingroup$ I have updated my answer after reviewing your question and comments. $\endgroup$ – Carl Christian Sep 29 '17 at 11:26
0
$\begingroup$

EDIT:

1) Yes. There is something which can be done. Let $A$ an $m$ by $n$ matrix and let $B$ by an $n$ by $k$ matrix with $n < k < m$. Then $AB$ is defined, but $BA$ is not. Augment $B$ with $m-k$ columns of zeros, so that $C = [B \: 0]$ is $n$ by $m$. This is a trivial extension of the operator $B$ to a larger subspace. Then $AC$ and $CA$ are both defined. The matrix $AC$ is $m$ by $m$ (large), while the matrix $CA$ is $n$ by $n$, but they have the same nonzero eigenvalues.

2) No. In general, there is little which can be learned from the separate analysis of $A$ and $B$. One extreme example is the case of nonsingular $A$ and $B = A^{-1}$. The work involved in producing from scratch the eigendecomposition of $A$ and $B$ is all for naught, as $AB = I$. Another example is the case where $A$ and $B$ are block diagonal matrices with $$A = \begin{bmatrix} A_{11} & 0 \\ 0 & 0 \end{bmatrix}, \quad B = \begin{bmatrix} 0 & 0 \\ 0 & B_{22} \end{bmatrix},$$ so that $AB=0$.


Original answer:

This may not be the answer that you are looking for, but knowing the SVD decomposition of a matrix is frequently useful and it might very well solve your underlying problem.

First let me justify a slight change in notation. By convention, vectors are column vectors unless explicitly identified as row vectors and this convention carries to rectangular matrices.

Here we are interested in a product $AB^T$ where $A \in \mathbb{R}^{m \times n}$ and $B \in \mathbb{R}^{k \times n}$ are tall matrices, i.e. $n \ll m$ and $n \ll k$. In particular, $m$ and $k$ are so large that we have neither the space to store the product explicitly nor the time to compute the SVD of the product even if enough storage could be made available.

Below follow the standard trick for this situation.

We can compute economy size QR factorizations of $A$ and $B$, i.e. $$A = QR, \quad B = VS,$$ where $Q \in \mathbb{R}^{m \times n}$ and $R \in \mathbb{R}^{n \times n}$, and $V \in \mathbb{R}^{k \times n}$ and $S \in \mathbb{R}^{n \times n}$. This is essentially Gram-Schmidt orthogonalization of $A$ and $B$. The costs are $O(mn^2)$ and $O(kn^2)$ arithmetic operations. Then $$AB^T = QRS^T V^T.$$

The small matrix $RS^T \in \mathbb{R}^{n \times n}$ requires $O(n^3)$ operations to form and another $O(n^3)$ operations to obtain its SVD, i.e. $$ RS^T = \bar{Q} \Sigma \bar{V}^T. $$ Returning to the product $AB^T$, we see that we have in fact computed its SVD, as $$ AB^T = Q R S^T V^T = Q \bar{Q} \Sigma \bar{V}^T V^T = (Q \bar{Q}) \Sigma (V \bar{V})^T.$$

$\endgroup$
  • $\begingroup$ Thank you, Carl. However, this does not really answer my question. My goal is not necessarily to do an SVD, but more to get a theoretical understanding of the link between eigenvalues for AB and for BA. $\endgroup$ – LBogaardt Sep 28 '17 at 7:51
  • $\begingroup$ Thanks for the update. The extension/embedding of $B$ in a larger space is clever and simple. It makes intuitive sense to me, but can you prove that it will always work? Also, $AB$ is rectangular - can we even determine its eigenvalues (see math.stackexchange.com/questions/2448088/…)? $\endgroup$ – LBogaardt Sep 29 '17 at 20:03
  • $\begingroup$ @LBogaardt I do not see what there is left to prove? I have done "something" to either $A$ or $B$, such that the (new) products $BA$ and $AB$ are defined and such that the nonzero eigenvalues are identical. Moreover, I have answered your second question contained in the last paragraph of your post. You can define eigenvalues for rectangular matrices, but the utility of the concept is rather limited, as most rectangular matrices have no eigenvalues and those that do lose them if their are perturbed slightly, see "Pseudospectra of rectangular matrices" by Wright and Trefethen. $\endgroup$ – Carl Christian Sep 29 '17 at 21:00
  • $\begingroup$ You have done something such that $AC$ and $CA$ are defined and such that both have identical eigenvalues. But what can be said about the eigenvalues of $AB$? Do $AB$ and $AC$ have the same eigenvalues? $\endgroup$ – LBogaardt Sep 30 '17 at 15:23
0
$\begingroup$

The following suggestion is based on https://arxiv.org/abs/0909.4061v2 and its references.

The larger matrix $A$ can be projected to a subspace of dimensions equal to those of $B$, without losing much/any of its action.

Steps:

  • Generate a random $n \times k$ matrix $\Omega$ from a Gaussian distribution with $\mu = 0$ and $\sigma = 1$
  • Form the $m \times k$ matrix $Y = AΩ$
  • Construct an $m \times k$ matrix $Q$ whose columns form an orthonormal basis for the range of $Y$, e.g. using the QR factorization $Y = QR$
  • Form the $n \times k$ matrix $\tilde{A} = Q^{∗}A$

Now, the product $B\tilde{A}$ is possible. The eigenvalues for this product are very close to the eigenvalues of the product $AB$.

The difference between the real $A$ and its approximation $\tilde{A}$ is given by $||A-QQ^{∗}A||$.

I do not have proof of this, and I am not sure this will work in all cases, but some quick tests seem to suggest it works.

$\endgroup$
  • $\begingroup$ I might be confusing singular-values with eigenvalues. If anyone could enlighten me on the difference within this context, I would be grateful. I created a similar question here: math.stackexchange.com/questions/2448088/… $\endgroup$ – LBogaardt Sep 28 '17 at 7:55

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.