McGill University

OPT 372

Handed out: 2023-01-26.
1. (This question provides a concrete algorithm for the theorem from lecture stating that
k independent vectors in Rn may be extended to a basis of Rn.)
Given k linearly independent vectors v1, . . . , vk ∈ Rn, let V denote the n × k matrix
[v1, . . . , vk] and consider performing QR factorization on this matrix, where the factors
are denoted Q ∈ Rn×n and R ∈ Rn×k as usual. Show that
[v1, . . . , vk, Q(:, k + 1), . . . , Q(:, n)]
is a basis for Rn.
Solution. Solution 1, using vectors. Note that [Q(:, 1), . . . , Q(:, n)] is a basis of Rn since
orthogonal matrices are invertible. Consider an arbitrary vector w in Rn. Since the
columns of Q form a basis of Rn, we can write w = Qy = y1Q(:, 1)+· · ·+ynQ(:, n) for
some vector y ∈ Rn. But according to the theorem in lecture, [Q(:, 1), . . . , Q(:, k)] is
an orthonormal basis of span{v1, . . . , vk}. Since v1, . . . vk are independent, this means
that they are a basis for span{Q(:, 1), . . . , Q(:, k)}. In other words, we can write y1Q(:
, 1)+· · ·+ykQ(:, k) as z1v1+· · ·+zkvk for some other coefficients z1, . . . , zk. Therefore,
the original w may be written as z1v1 + · · · + zkvk + yk+1Q(:, k + 1) + · · · + ynQ(:, n).
Since w was arbitrary, this shows that v1, . . . , vk, Q(:, k + 1), . . . , Q(:, n) form a basis
of Rn (because they are spanning and there are n vectors in this sequence).
Solution 2, using orthogonal complement theorem. Say x ∈ Rn is arbitrary. Using the
orthogonal complement theorem, we can write x := y+z, where y ∈ span{v1, . . . , vk} =
Range(V ) and z ∈ span{v1, . . . , vk}⊥ = Range(V )⊥ = span{Q(:, k + 1), . . . , Q(:, n)}.
Here, the last equality follows from the QR-factorization theorem. Therefore, we have
proved that every vector in Rn can be written as a linear combination of the columns
of V and the columns of Q(:, k + 1 : n), i.e., the columns of [V, Q(:, k + 1 : n)] span Rn.
Solution 3, using block matrices. Observe that, as in lecture, since V = QR, then
V = Q(:, 1 : k)R(1 : k, 1 : k) and therefore
[V, Q(:, k + 1 : n)] = [Q(:, 1 : k)R(1 : k, 1 : k), Q(:, k + 1 : n)]
= [Q(:, 1 : k), Q(:, k + 1 : n)]  R(1 : k, 0 1 : k) 0 I  ,
where the identity matrix in the previous line is of size (n - k) × (n - k). The last
line is a product of two invertible matrices: the first matrix is Q, which is invertible
1
This study source was downloaded by 100000870048475 from CourseHero.com on 09-19-2023 22:47:34 GMT -05:00
https://www.coursehero.com/file/196005321/ps1solpdf/
since it is orthogonal. The second matrix is invertible because we can directly write
its inverse:
 R(1 : k,01 : k)-1 I0 
and confirm that this is the correct inverse by multiplying it by the second factor.
(Note: we use here the fact that R(:, 1 : k, 1 : k) is invertible by the QR-factorization
theorem.) Therefore, we conclude that [V, Q(:, k + 1 : n)] is invertible, which means
that its columns form a basis for Rn.
2. Let A ∈ Rm×n be a matrix whose rank is m (so necessarily, m ≤ n). In this case,
the system of equations Ax = b always has at least one solution x for any choice of
b ∈ Rm. Here is an algorithm to find this solution: Factor AT = QR = Q1R1 where
Q1 = Q(1 : n, 1 : m) and R1 = R(1 : m, 1 : m) as in lecture. Then let x := Q1R1-T b.
(a) Why do we know R1-T exists?
(b) By substitution, show that x from the above formula indeed satisfies Ax = b.
Solution. (a) Since rank(A) = m, then rank(AT ) = m. It follows from the theorem in
lecture that an n × m matrix whose rank is m has a QR