In the following paper:

Restricted Rank Modification of the Symmetric Eigenvalue Problem: Theoretical Considerations

on page 79, Golub et al. have the following set of equations:

$f(\lambda) = \text{det}(I_r - U^T(\lambda - \Lambda)^{-1}U) \quad ... (1) \\ \quad =1 + \sum_{k=1}^r (-1)^k \sum_{\tau_k=1}^r\sum_{j_k=1}^n\frac{(\text{det}U_{j_1,...,j_k;\tau_1,...,\tau_k})^2}{(\lambda - \lambda_{j_1})...(\lambda - \lambda_{j_k})} \quad ... (2)$


$U_{j_1,...,j_k;\tau_1,...,\tau_k} = \begin{bmatrix}e^T_{j_1}\\ \vdots\\e^T_{j_k}\end{bmatrix} U \begin{bmatrix}e_{\tau_1}&\ldots& e_{\tau_k}\end{bmatrix}$,

and $\Lambda = \text{diag}(\lambda_1,...\lambda_n)$ are the eigenvalues for a matrix $A = Q\Lambda Q^T \in \mathbb{R}^{n \times n}$ and $V=QU$.

Moreover although not explicitly stated in the paper, we infer that $\begin{bmatrix}e^T_{j_1}& \ldots &e^T_{j_k}\end{bmatrix}^T \in \mathbb{R}^{n\times k}$ and $\begin{bmatrix}e_{\tau_1}&\ldots& e_{\tau_k}\end{bmatrix} \in \mathbb{R}^{r\times k}$ since, $U \in\mathbb{R}^{n \times r}$ so that the units vectors, $e_{j_k}$ live in $n$ dimensions, and $e_{\tau_k}$ likes in $r$ dimensions

However I am not sure how he goes from one line to the other (i.e. from Equation (1) to Equation (2)).

Golub et al. state that is fairly trivial and it exploits the multi-linearity property of the determinant, however I cannot seem formulate the steps.

Let me know if you require any further information.

  • $\begingroup$ It seems that $U$ is of dimension $n \times r$. I don't understand, then, who is $k$ in the formula of $\det U_{j_1, \dots, j_k; \tau_1, \dots, \tau_k}$. Also, you have an extra transposition at the end of the same line. $\endgroup$
    – Alex M.
    Sep 28, 2018 at 11:12
  • $\begingroup$ Hi Alex, thanks for picking up on the transpose you are correct. As for "k" it is the iteration index, which I believe is entirely separate to $\tau_k$ and $j_k$, or that's how at least I interpret his notation. I'm not sure of his motivation for using $k$ everywhere. I was hoping that if someone could break down how he gets one line from the other it would help clarify these understanding / notation issues for me. A few more steps breaking it down would help immensely. $\endgroup$ Sep 28, 2018 at 12:12
  • $\begingroup$ If I understand correctly, the $e_i$ are the vectors in the canonical basis of $\mathbb R^n$. Then $U_{j_1,...,j_k;\tau_1,...,\tau_k}$ is a product of a $k \times n$, a $n \times r$ and a $n \times k$ matrices. Notice, then, that the last two matrices can't really be multiplied - unless the vectors $e_i$ on the right of $U$ live in $\mathbb R ^r$ (unlike the ones on the left of $U$, which live in $\mathbb R^n$). If so, then the authors have used the same notations for vectors living in different spaces. Also, there is an extra "$\det$" at the beginning of the same line. $\endgroup$
    – Alex M.
    Sep 28, 2018 at 12:46
  • $\begingroup$ Hi Alex those are good points, not sure why I didn't notice them before. I agree with your statement, perhaps the $e_{\tau_k}$ are indeed living in an r-dimensional space, even though the author did not explicitly state this anywhere. But now this confuses me even more, as to how he arrives at the second equation. :/ I'll re-update your suggestions changes in the original question. Thanks. $\endgroup$ Sep 28, 2018 at 13:36


Your Answer

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