MAS400: Solutions 8

All questions have the following. Let v_{1}, …, v_{n} be linearly independent vectors in ℝ^{n}, such that (v_{1}, …, v_{n}) has Gram–Schmidt orthogonalisation ((v_{1}^{∗}, …, v_{n}^{∗}), (μ_{st})). Determine the Gram–Schmidt orthogonalisations ((w_{1}^{∗}, …, w_{n}^{∗}), (ξ_{st})) of (w_{1}, …, w_{n}) in the following cases. Throughout, I shall assume well-known properties of the GSO such as ⟨v_{1}^{∗}, …, v_{k}^{∗}⟩_{ℝ} = ⟨v_{1}, …, v_{k}⟩_{ℝ} for all k, and that v_{k}^{∗} is the (orthogonal) projection of v_{k} onto ⟨v_{1}, …, v_{k−1}⟩_{ℝ}^{⊥} for all k.

Throughout, let V_{k} = ⟨v_{1}, …, v_{k}⟩ = ⟨v_{1}^{∗}, …, v_{k}^{∗}⟩ and W_{k} = ⟨w_{1}, …, w_{k}⟩, for all k with 0 ⩽ k ⩽ n.

1. Case w_{i} = λv_{i}, w_{j} = v_{j} if j ≠ i, where λ ≠ 0 (λ ∈ ℝ).

In this case V_{k} = W_{k} for all k, including the case k = i. Since w_{k} = v_{k} if k ≠ i then clearly w_{k}^{∗} = v_{k}^{∗} for such k. Now w_{i}^{∗} is the orthogonal projection of w_{i} = λv_{i} onto W_{i−1}^{⊥} = V_{i−1}^{⊥}, and so w_{i}^{∗} = λv_{i}^{∗}. This deals with the GSO basis. The only pairs (s, t) where ξ_{st} might differ from μ_{st} are those for which s > t and where w_{s} ≠ v_{s} or w_{t}^{∗} ≠ v_{t}^{∗}. Thus ξ_{st} = μ_{st} unless i = s > t or s > t = i. In the case i = s > t we have ξ_{st} = ξ_{it} = \frac{w_{i}·w_{t}^{∗}}{w_{t}^{∗}·w_{t}^{∗}} = \frac{(λv_{i})·v_{t}^{∗}}{v_{t}^{∗}·v_{t}^{∗}} = λ\frac{v_{i}·v_{t}^{∗}}{v_{t}^{∗}·v_{t}^{∗}} = λμ_{it} = λμ_{st}. In the case s > t = i

we have ξ_{st} = ξ_{si} = \frac{w_{s}·w_{i}^{∗}}{w_{i}^{∗}·w_{i}^{∗}} = \frac{v_{s}·(λv_{i}^{∗})}{(λv_{i}^{∗})·(λv_{i}^{∗})} = \frac{1}{λ} \frac{v_{s}·v_{i}^{∗}}{v_{i}^{∗}·v_{i}^{∗}} = (\frac{1}{λ})μ_{si} = (\frac{1}{λ})μ_{st}.

2. Case w_{i} = v_{i} − λv_{k} with k < i, w_{j} = v_{j} if j ≠ i.

But for all k < i we have w_{k} = v_{k} and thus W_{k} = V_{k} for all k < i. Now v_{i} − w_{i} = λv_{j} ∈ V_{j} ⊆ V_{i−1}, and so W_{i} = V_{i} too. Since w_{k} = v_{k} for k > i we conclude that W_{k} = V_{k} for all k. Firstly, let us consider the GSO bases. For all k, v_{k}^{∗} is the projection of v_{k} onto V_{k−1}^{⊥} ∩ V_{k}. Also w_{k}^{∗} is the projection of w_{k} onto W_{k−1}^{⊥} ∩ W_{k} = V_{k−1}^{⊥} ∩ V_{k}, and since w_{k} − v_{k} ∈ V_{k−1} for all k we get that w_{k}^{∗} = v_{k}^{∗} for all k. If k < l then ξ_{kl} = μ_{kl} = 0 and if k = l then ξ_{kl} = μ_{kl} = 1. In the main case when k > l we have ξ_{kl} = \frac{w_{k}·w_{l}^{∗}}{w_{l}^{∗}·w_{l}^{∗}} = \frac{w_{k}·v_{l}^{∗}}{v_{l}^{∗}·v_{l}^{∗}}. So if k ≠ i we have w_{k} = v_{k} and thus ξ_{kl} = μ_{kl}. If k = i then w_{k} = w_{i} = v_{i} − λv_{j}. Therefore we have ξ_{il} = \frac{w_{i}·v_{l}^{∗}}{v_{l}^{∗}·v_{l}^{∗}} = \frac{(v_{i}−λv_{j})·v_{l}^{∗}}{v_{l}^{∗}·v_{l}^{∗}} = \frac{v_{i}·v_{l}^{∗}}{v_{l}^{∗}·v_{l}^{∗}} − λ\frac{v_{j}·v_{l}^{∗}}{v_{l}^{∗}·v_{l}^{∗}} = μ_{il} − λ\frac{v_{j}·v_{l}^{∗}}{v_{l}^{∗}·v_{l}^{∗}}, which is μ_{il} − λμ_{jl} if l < j. Note that v_{k} · v_{l}^{∗} = 0 if k < l as v_{k} ∈ V_{l−1}, which is perpendicular to v_{l}^{∗}. Also (v_{k} − v_{k}^{∗}) ∈ V_{k−1}, which is perpendicular to v_{k}^{∗}, and so v_{k} · v_{k}^{∗} = v_{k}^{∗} · v_{k}^{∗} for all k. Thus ξ_{ij} = μ_{ij} − λ = μ_{ij} − λμ_{jj} and ξ_{il} = μ_{il} = μ_{il} − λμ_{jl} if j < l < i. Therefore ξ_{il} = μ_{il} − λμ_{jl} whenever l < i.

3. Case w_{i} = v_{i+1}, w_{i+1} = v_{i}, w_{j} = v_{j} if j ≠ i, i + 1.

Firstly, let us consider the GSO bases. For all k, v_{k}^{∗} is the projection of v_{k} onto V_{k−1}^{⊥} ∩ V_{k}. If k ≠ i, i + 1 then W_{k−1} = V_{k−1} and W_{k} = V_{k} and so w_{k}^{∗} = v_{k}^{∗} for all such k. Similarly V_{i−1} = W_{i−1} and V_{i+1} = W_{i+1} and so U := ⟨v_{i}^{∗}, v_{i+1}^{∗}⟩ = ⟨w_{i}^{∗}, w_{i+1}^{∗}⟩. Now V_{i+1} is the direct sum of U and V_{i−1}. Thus considering the U-components of v_{i} = w_{i+1} and v_{i+1} = w_{i} gives the equations:

\begin{matrix}w_{i+1}^{∗} + ξ_{i+1,i}w_{i}^{∗} = & v_{i}^{∗}, \\ w_{i}^{∗} = & v_{i+1}^{∗} + μ_{i+1,i}v_{i}^{∗}. \end{matrix}

Therefore, w_{i+1}^{∗} = v_{i}^{∗} − ξ_{i+1,i}w_{i}^{∗} = −ξ_{i+1,i}v_{i+1}^{∗} + (1 − ξ_{i+1,i}μ_{i+1,i})v_{i}^{∗}. The inner product 0 = w_{i+1}^{∗} · w_{i}^{∗} gives the equation:

ξ_{i+1,i}(v_{i+1}^{∗} · v_{i+1}^{∗} + μ_{i+1,i}μ̄_{i+1,i}v_{i}^{∗} · v_{i}^{∗}) = μ̄_{i+1,i}(v_{i}^{∗} · v_{i}^{∗}),

which allows one to determine ξ_{i+1,i} in terms of the μs and v^{∗}s. (Note that v_{i+1}^{∗} ·v_{i+1}^{∗} +μ_{i+1,i}μ̄_{i+1,i}v_{i}^{∗} ·v_{i}^{∗} is in fact w_{i}^{∗} ·w_{i}^{∗}, and is thus nonzero.) Thus w_{i+1}^{∗} can be written in terms of the μs and v^{∗}s.

Now we consider (most of) the ξ_{kl}. If k = l then ξ_{kl} = μ_{kl} = 1 and if k < l then ξ_{kl} = μ_{kl} = 0. Also if k, l ∉ {i, i + 1} then the relevant vs and ws are equal and so ξ_{kl} = μ_{kl} in these cases too. If k ⩽ i − 1 then ξ_{i,k} = \frac{w_{i}·w_{k}^{∗}}{w_{k}^{∗}·w_{k}^{∗}} = \frac{v_{i+1}·v_{k}^{∗}}{v_{k}^{∗}·v_{k}^{∗}} = μ_{i+1,k} and ξ_{i+1,k} = \frac{w_{i+1}·w_{k}^{∗}}{w_{k}^{∗}·w_{k}^{∗}} = \frac{v_{i}·v_{k}^{∗}}{v_{k}^{∗}·v_{k}^{∗}} = μ_{i,k}. The remaining cases are nastier. (Recall that we have already calculated w_{i}^{∗}, w_{i+1}^{∗} and ξ_{i+1,i} in terms of the μs and v^{∗}s.) For all k > i + 1 we have:

\begin{matrix}(w_{i}^{∗} · w_{i}^{∗})ξ_{ki} = & w_{k} · w_{i}^{∗} = v_{k} · (v_{i+1}^{∗} + μ_{i+1,i}v_{i}^{∗}) \\ = & v_{k} · v_{i+1}^{∗} + μ̄_{i+1,i}(v_{k} · v_{i}^{∗}) \\ = & (v_{i+1}^{∗} · v_{i+1}^{∗})μ_{k,i+1} + μ̄_{i+1,i}(v_{i}^{∗} · v_{i}^{∗})μ_{ki}, \end{matrix}

along with:

\begin{matrix}(w_{i+1}^{∗} · w_{i+1}^{∗})ξ_{k,i+1} = & w_{k} · w_{i+1}^{∗} = v_{k} · (−ξ_{i+1,i}v_{i+1}^{∗} + (1 − ξ_{i+1,i}μ_{i+1,i})v_{i}^{∗}) \\ = & −ξ̄_{i+1,i}(v_{k} · v_{i+1}^{∗}) + (1 − ξ̄_{i+1,i}μ̄_{i+1,i})(v_{k} · v_{i}^{∗}) \\ = & −ξ̄_{i+1,i}(v_{i+1}^{∗} · v_{i+1}^{∗})μ_{k,i+1} + (1 − ξ̄_{i+1,i}μ̄_{i+1,i})(v_{i}^{∗} · v_{i}^{∗})μ_{ki}. \end{matrix}

We have already calculated that ξ_{i+1,i} = μ̄_{i+1,i} \frac{v_{i}^{∗}·v_{i}^{∗}}{w_{i}^{∗}·w_{i}^{∗}} above.

I shall make only the briefest of remarks about the remaining questions, which (try to) detail what happens to the GSO when the remaining elementary row operations are applied to a basis. The ones relevant for BasisReduction are in Questions 2 and 3. In both the remaining cases, one is usually better off calculating the new GSO from scratch.

4. Case w_{i} = v_{i} − λv_{k} with k > i, w_{j} = v_{j} if j ≠ i.

(This should be contrasted with the answer to Question 2.)

5. Case w_{i} = v_{k}, w_{k} = v_{i} (wlog i < k), w_{j} = v_{j} if j ≠ i, k.

(This is significantly more complicated than the answer to Question 3.)

In both of these remaining cases, we have W_{j} = V_{j} if j < i or j ⩾ k. Thus w_{j}^{∗} = v_{j}^{∗} if j < i or j > k. Therefore ξ_{jl} = μ_{jl} whenever j ⩽ l or (l < i and j ∉ {i, k}) or j, l > k. One can expect that w_{j}^{∗} ≠ v_{j}^{∗} if i ⩽ j ⩽ k, and the formulae involved here are not pleasant. I shall not even comment on the remaining ξ_{jl}.