11
$\begingroup$

I have a matrix of quite special form: $$S=A'A$$ $$A=\begin{bmatrix} 1 &0 &\dots &0 \\ 0 &1 &\dots &0 \\ 0 &0 &\dots &1 \\ a_{1} &a_{2} &\dots &a_{n} \end{bmatrix}$$ Thus $A$ is a $(n+1)\times n$ and $S$ is $n\times n$ symmetric matrix. I am wondering if there is some name for the matrices like $A$. I am implementing some numerical algorithm and I need to find inverses and square roots of very large matrices $S$. Since the matrix I am dealing with is of quite simple form, maybe there are some properties that would allow fast square root computations.

Maybe some members of this community has some insight on how to make square root calculations faster. Does the matrix have a name I can research?

$\endgroup$
  • $\begingroup$ Looks slightly like the Läuchli matrix... $\endgroup$ – J. M. is a poor mathematician Nov 14 '17 at 11:37
  • 4
    $\begingroup$ $A=\begin{bmatrix}I \\ a^T\end{bmatrix}$ where $a$ is a column vector, so $S = A^TA = I + aa^T$ is just a rank-one perturbation of the identity matrix. From this fact it is easy to find its inverse and square root. $\endgroup$ – Rahul Jul 18 '18 at 11:12
  • $\begingroup$ FYI: $S = [\delta_{ij} + a_ia_j]_{1 \le i, j \le n}$, $\det S = 1 + a_1^2 + \dotsb + a_n^2$, and $S^{-1} = \tfrac{1}{\det S}[\delta_{ij}\det S - a_ia_j]_{1 \le i, j \le n}$ if $a_1, \dotsc, a_n \in \mathbf{R}$ and $a_1 \neq 0$. $\endgroup$ – Orat Jul 18 '18 at 11:14
  • 2
    $\begingroup$ $A$ is the transpose of the companion matrix (see: en.wikipedia.org/wiki/Companion_matrix ) of the monic polynomial $-a_1-a_2 t-...-a_n t^n + t^{n+1}$, with a row $[1,0,...,0]$ added $\endgroup$ – Bob Jul 18 '18 at 11:36
  • $\begingroup$ It looks like a companion matrix. Or yeah transpose of companion matrix. $\endgroup$ – mathreadler Jul 18 '18 at 12:05
5
+25
$\begingroup$

To follow up on Rahul's comment, we wish to find a matrix $M$ such that $$M^2 = S = I + aa^T$$ Let's denote the length and direction of the $a$-vector as separate variables $$\eqalign{ \lambda^2 &= a^Ta &\implies \lambda = \|a\| \cr n &= \lambda^{-1}a\cr }$$ Construct the ortho-projector $P=(I-nn^T)$ with properties $$P^2 = P = P^T,\,\,\,\, Pn=0$$ Now consider this $$\eqalign{ (P+\beta nn^T)^2 &= P + \beta^2 nn^T \cr &= I + (\beta^2-1)nn^T\cr &= I + \tfrac{(\beta^2-1)}{\lambda^2}aa^T\cr }$$ Selecting $\,\beta={\sqrt{\lambda^2+1}}\,$ yields $$(P+\beta nn^T)^2 = I+aa^T = S$$ Therefore $$\eqalign{ {\sqrt S} &= P+\beta nn^T \cr &= I + (\beta-1)nn^T \cr &= I + \frac{\beta-1}{\lambda^2}aa^T \cr &= I + \frac{\beta-1}{\beta^2-1}aa^T \cr &= I + \frac{aa^T}{1+\beta} \cr &= I + \frac{aa^T}{1+\sqrt{a^Ta+1}} \cr\cr }$$ The inverse can be handled using the Sherman-Morrison formula $$\eqalign{ S^{-1} &= (I+aa^T)^{-1} \cr &= I - \frac{aa^T}{1+a^Ta} \cr\cr }$$ Bonus result:
Any function of $\,S=(I+aa^T)\,$ can be written as $$f(S) = \bigg(\frac{f(a^Ta+1)-f(1)}{a^Ta}\bigg)\,aa^T + f(1)\,I $$ Start with a formula (427) from the Matrix Cookbook (for idempotent $A$) $$f(sI+tA) = (I-A)\,f(s) + A\,f(s+t)$$ and substitute $\,s=1,\,\,t=a^Ta,\,\,A=\frac{aa^T}{a^Ta}$

$\endgroup$
3
$\begingroup$

I don't know a name for this kind of matrix, but here is some insight on the square root, obtained from limited empirical evidence:

  • The eigenvalues of $S$ are $\lambda=1$ with multiplicity $n - 1$ and $\mu=1 + a_1^2 + \dots + a_n^2$ with multiplicity $1$.

  • The eigenvectors for $\lambda$ are $v_2=(-a_2, a_1, 0, 0, \dots, 0)$, $v_3=(-a_3, 0, a_1, 0, \dots, 0)$, $v_4=(-a_4, 0, 0, a_1, \dots, 0)$, $\dots$, $v_n=(-a_n, 0, 0, 0, \dots, a_1)$.

  • The eigenvectors for $\mu$ is $v_1=(a_1, \dots, a_n)$.

Then a square root for $S$ is $P \operatorname{diag}(\sqrt\mu,1,\dots,1)P^{-1}$, where $P$ is the matrix of eigenvectors.

$\endgroup$
  • $\begingroup$ What are the names, then? $\endgroup$ – Orat Jul 18 '18 at 12:17
2
$\begingroup$

$$A=\begin{bmatrix}I \\ a^{T}\end{bmatrix}\to\\S=A'A=A=\begin{bmatrix}I & a\end{bmatrix}\begin{bmatrix}I \\ a^{T}\end{bmatrix}=I+aa^T$$since $aa^T$ is of rank 1 it has $n-1$ zero eigenvalues and one $a^Ta$ eigenvalue therefore the eigenvalues of $S$ include $n-1$ of 1 and one $1+a^Ta$ so $S$ is invertible if and only if $$a^Ta\ne -1$$ also we have that$$S^2=(I+aa^T)(I+aa^T)=I+2aa^T+aa^Taa^T=I+2aa^T+(a^Ta)aa^T=I+(2+a^Ta)aa^T=(2+a^Ta)S-(1+a^Ta)I$$if $S$ is invertible therefore $$S=(2+a^Ta)I-(1+a^Ta)S^{-1}$$or $$S^{-1}=\dfrac{1}{1+a^Ta}\left((2+a^Ta)I-I-aa^T\right)=I-\dfrac{1}{1+a^Ta}aa^T$$now for finding the powers of $S$ let $$S^k=(1+t_k)S-t_kI$$multiplying by $S$ yields to $$S^{k+1}=(1+t_k)S^2-t_kS=(2+a^Ta+(1+a^Ta)t_k)S-(1+a^Ta)(1+t_k)I=(1+t_{k+1})S-t_{k+1}I$$therefore$$t_{k+1}=(1+a^Ta)(1+t_k)$$it's not hard to see that $$t_k=\dfrac{(1+a^Ta)^k-1-a^Ta}{a^Ta}$$and we have $$S^k=\dfrac{(1+a^Ta)^k-1}{a^Ta}S-\dfrac{(1+a^Ta)^k-1-a^Ta}{a^Ta}I$$or $$\LARGE S^n=I+\dfrac{(1+a^Ta)^n-1}{a^Ta}aa^T\quad,\quad n\in\Bbb Z$$it is interesting that the above equation holds even for negative $n$s (prove as a good exercise!). Also if $\hat{S}$ is such that $\hat{S}^2=S$ then the eigenvalues of $\hat{S}$ are $n-1$ 1 and one $\sqrt{1+a^Ta}$ which means that $$\hat{S}=I+kaa^T$$ for some k. Therefore $$\hat{S}^2=I+(k^2+2k)aa^T$$which means that $$k=\dfrac{1}{1+\sqrt{1+a^Ta}}$$and finally we obtain$$\LARGE S^{\frac{1}{2}}=I+\dfrac{1}{1+\sqrt{1+a^Ta}}aa^T$$

$\endgroup$
1
$\begingroup$

As Rahul already told us, a symmetric matrix like $S$ is called a rank-one perturbation of the identity matrix. I also found a page (Woodbury matrix identity) that refers to matrices of this kind as rank-one correction of the identity matrix. On the same page, I also found a term capacitance matrices, which include the above-mentioned matrices.

Unfortunately, I could not find a name for a rectangular matrix like $A$.

$\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.