正定値対称行列$A\in {\mathbb R}^{n\times n}$に対して、$A=RR^\top$なる下三角行列$R\in {\mathbb R}^{n\times n}$が存在します(この証明は省略します)。成分で書くと
$$ A_{ji}=\sum_{h=1}^nR_{jh}R_{ih},\hspace{5mm}i,j=1,\ldots,n$$ が成立します。最初に$R_{ij}$, $i,j=1,\ldots,n$ をすべて0にしてから、各$i=1,\ldots,n$で
1. $R_{ii}=\sqrt{A_{ii}-\sum_{h=1}^{i-1}R_{ih}^2}$
2. $R_{ji}=(A_{ji}-\sum_{h=1}^{i-1}R_{jh}R_{ih})/R_{ii}$, $\hspace{3mm}j=i+1,\ldots,n$
によって、$R$の第$i$列が求まります。2.は$(n-i)^2$回の演算(乗算)が必要で、全体で
$$\sum_{i=1}^n(n-i)^2=\sum_{j=0}^{n-1}j^2=\frac{1}{6}(n-1)n(2(n-1)-1)=\frac{n^3}{3}(1-\frac{1}{n})(1-\frac{1}{2n})$$回、高々$n^3/3$の演算が必要です。他方、$A,B\in {\mathbb R}^{n\times n}$の乗算は、その第$i,j$成分が$\sum_{h=1}^n A_{ih}B_{hj}$によって得られ、この操作を$n^2$個の成分すべてに対して行うので、$n^3$回の演算が必要です。$A$の逆行列を求める操作も同様の時間を要します。

計算量のオーダー表現は、定数倍の差異を除いて考えるので、上記すべて$O(n^3)$という表記が本来ですが、機械学習のためのカーネル6.1節では、$O(n^3/3)$, $O(n^3)$というように両者を区別しています。

また、下三角行列$L\in {\mathbb R}^{n\times n}$とある定数ベクトル$b\in {\mathbb R}^{n}$があって、$Lx=b$なる$x$を求めるためには、$$x_i=(b_i-\sum_{h=1}^{i-1}L_{i,j}x_j)/L_{ii}$$を各$i=1,\ldots,n$に対して行う必要があり、高々$1+\ldots+(n-1)=n(n-1)/2$回の乗算が必要です。テキストではこれを$O(n^2)$の時間がかかるとしています。