Write an algorithm which takes a set of vectors as input and returns an orthonormal set of vectors generated from the given set
Answers
Answer: Let K be a given integer, with K even (and "large"). Let v∈RK×1 be a given non-zero (column) vector. Write a (possibly efficient) algorithm to construct a matrix B∈RK×K−1 such as that: (1) the column-vectors of B are orthogonal to each other; (2) BTv=0, where T denotes transpose and 0 a ((K-1)-dimensional) vector of all zeros.
Denoting with bi, i=1,…,K−1, the i-th column of B, the first requirement can be rewritten as: b
T
i
bj=0 for i≠j.
Essentially, the problem asks to write an algorithm to find an orthogonal basis to the orthogonal complement of the (mono-dimensional) space spanned by v. The algorithm can be written in pseudo-code (or in MATLAB-like or in C-like code). The algorithm takes in input the vector v and the integer K; its output is the matrix B.Note: the algorithm cannot do a "random trial-and-error", i.e., generate a random vector, try if it is orthogonal to v and to the previously found columns of B, discard if it not, memorize it if it is. This is an explicitly forbidden brute-force approach. However, it is indeed allowed to do this as an initializing stage, i.e., for the first column of the matrix or as a "random guess" at the start, if any need to do so should arise. "Normality", i.e., finding an orthonormal basis, is not required. Input checking (e.g. checking if K is an even integer) is not required.