Representation of elementary matrix in numerical computation

Let $u = [u_1, u_2,..., u_n]$ and $v = [v_1, v_2, ..., v_n]$. Then $uv^T$ is a rank-1 matrix. Then the definition of elementary matrix says: Elementary matrices are rank-1 changes to the identity matrix: $I + uv^T$. (and hence we only have to store $u$ and $v$ to represent elementary matrix)

I'm not sure how this definition can be true. How do we find $u$ and $v$ to enforce every single elementary row operation?

• Storing two full vectors $u,v$ is overkill to represent elementary matrices, but you can certainly do it that way. – hardmath Feb 3 '18 at 22:12

We just have to check the matrices of the three known types of elementary row operations:

Type I: Row Switching

These matrices have the form

$$\begin{pmatrix} 1 & & & &\\ &0_{(i,i)} &\cdots &1_{(i,j)} &\\ &\vdots &1 &\vdots &\\ &1_{(j,i)} &\cdots &0_{(j,j)} &\\ & & & &1\\ \end{pmatrix}$$

And using $u = (0,\ldots,0,1,0,\ldots,0,-1,0,\ldots,0)^t$ (the nonzero entries at $i$ and $j$ respectively) and $v = -u$ we immediately get the above matrix with $I-uv^t$

These matrices have the form $$\begin{pmatrix} 1 & & & &\\ &1 & & &\\ & &1 & &\\ &r_{(i,j)} & & 1 &\\ & & & &1\\ \end{pmatrix}$$ This can be achieved using $u = (0,\ldots,0,-1,0,\ldots,0)^t$ where the $-1$ is in the $i-th$ position and $v = (0,\ldots,0,r_{(i,j)},0,\ldots,0)^t$ whre $r_{(i,j)}$ is in the $j$-th position
$$\begin{pmatrix} 1 & & & &\\ &1 & & &\\ & &c_{(i)} & &\\ & & & 1 &\\ & & & &1\\ \end{pmatrix}$$
This can be done using the type II with $r_{(i,i)} = c_{(i)}-1$.