1.1. Basic algorithms and notation

1 Given the product $\mathbf{M}$ $=$ $\mathbf{A} - x_n \mathbf{I}$, where $x_n$ runs from $1$ to $r$ and $\mathbf{A}$ and the identity matrix $\mathbf{I}$ are matrices in $\mathbb{R}^{n \times n}$, the first column of $\mathbf{M}$ can be computed by first multiplying the elements of $\mathbf{I}$ by $x_n$ for all $n$, and then performing pointwise subtraction between the matrices $\mathbf{A}$ and $x_n\mathbf{I}$.

$\text{\textbf{Algorithm 1}}$
$\text{\textbf{for}} \ i \ = \ 1:n$
$\qquad \mathbf{M}_{i} = \mathbf{A}_{i1} - x_i \mathbf{I}_{i1}$
$\text{\textbf{end}}$

So for example, if

$$ \mathbf{A} = \begin{bmatrix} a_{11} \ \ \ \cdots \\ a_{21} \ \ \ \cdots \\ a_{31} \ \ \ \cdots \\ \vdots \\ a_{n1} \ \ \ \cdots \end{bmatrix}, \quad \mathbf{x} = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}, $$

$$ \begin{array}{r c c} \mathbf{A} & = & \begin{bmatrix} a_{11} \ \ \ \cdots \\ a_{21} \ \ \ \cdots \\ a_{31} \ \ \ \cdots \\ \vdots \\ a_{n1} \ \ \ \cdots \end{bmatrix} , \\[1em] \mathbf{x} & = & \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix}, \end{array} $$

then the iterating the above algorithm results in the product

$$ \mathbf{M} = \begin{bmatrix} a_{11} - 1x_1 \\ a_{12} - 0x_2 \\ \vdots \\ a_{1n} - 0x_n \end{bmatrix} = \mathbf{A}_{i1} - x_i\mathbf{I}_{i1}, \qquad i = 1:n. $$

2 See this post.

3 For the given matrix $\mathbf{C} \in \mathbb{R}^{n \times n}$ and $n$-vectors $\mathbf{x}$ and $\mathbf{y}$,

$$ \mathbf{C} = (\mathbf{x} \mathbf{y}^\top)^k = (\mathbf{x} \mathbf{y}^\top) (\mathbf{x} \mathbf{y}^\top) \cdots (\mathbf{x} \mathbf{y}^\top) = \mathbf{x} \underbrace { (\mathbf{y}^\top \mathbf{x}) (\mathbf{y}^\top \mathbf{x}) \cdots (\mathbf{y}^\top \mathbf{x}) }_{k-1 \ \text{times}} \mathbf{y}^\top \tag{1} $$

and since dot product $\mathbf{y}^\top \mathbf{x}$ is a time complexity $O(n)$ operation show in the following algorithm as shown in the following algorithm

$\text{\textbf{Algorithm 3}: {\rm D{\small OT}P{\small RODUCT}}}$
$\text{\textbf{for}} \ i = 1 : n$
$\qquad d = d + \mathbf{y}^\top(i) \mathbf{x}(i) \ \color{gray}{// \ \text{or equivalently,} \ d = d + y_ix_i}$
$\text{\textbf{end}}$

where $d$ $=$ $0$ when $i$ $=$ $1$, the product of $\mathbf{x}$ and $\mathbf{y}^\top$, can be organized as computation where dot products $\mathbf{y}^\top_i \mathbf{x}_{i+1}$, from $i = 1$ to $k-1$, are first computed to get the scalar $a$, and because $\mathbf{x} a \mathbf{y}^\top$ $=$ $a \textbf{x} \mathbf{y}^\top$, the product $\mathbf{x} \mathbf{y}^\top$ can be computed using the algorithm

$\text{\textbf{Algorithm 4}: {\rm S{\small QR}M{\small AT}M{\small UL}}}$
$\text{\textbf{for}} \ i = 1 : n$
$\qquad \text{\textbf{for}} \ j = 1 : n$
$\qquad \qquad \mathbf{C}(i,j) = a \mathbf{x}(i)\mathbf{y}^\top(j) \ \color{gray}{// \ \text{or equivalently,} \ c_{ij} = ax_iy_j}$
$\qquad \text{\textbf{end}}$
$\text{\textbf{end}}$

that has time complexity $O(n^2)$. As this time complexity is the most dominant, the product

$$ \mathbf{C} = (\mathbf{x}\mathbf{y}^\top)^k $$

can be computed in $O(n^2)$ time with algorithm that first computes the scalar $d$ using $\text{\rm D{\small OT}P{\small RODUCT}}$ and uses that scalar when computing $\text{\rm S{\small QR}M{\small AT}M{\small UL}}$ between the leading vector $\mathbf{x}$ and trailing vector $\mathbf{y}^\top$ of the right hand-side of $\mathbf{C}$ in $(1)$.