Finding vectors orthonormal to a given vector set and the Gram-Schmidt process

Here is a likely very simple problem that I am confused about: Let $$\{v_k\}$$ be a set of vectors ($$k=1, ..., n$$). I would like to find a set of vectors $$\{q_k\}$$ such that

$$\langle q_i| v_j \rangle = \delta_{ij}$$

where $$\langle .| . \rangle$$ is the inner product (assume standard inner product for simplicity). We do not place any additional restrictions on the properties of $$\{q_k\}$$.

This question has (in modified form) already been asked on the network: Given a set of non orthogonal functions. Find another set of functions that are orthogonal to the first set.. The answer there links to the Gram-Schmidt process as the solution. I think I understand the latter, but I don't understand how it solves the above problem.

Specifically, I do not understand how the functions $$\{u_k\}$$ obtained from the Gram-Schmidt process (notation consistent with the wikipedia article above) correspond to the $$\{q_k\}$$, since the $$\{u_k\}$$ do not fulfill the required property. This can be seen straightforwardly, since $$u_1=v_1,$$ such that (assuming the $$\{v_k\}$$ are already normalized) $$\langle u_1| v_1 \rangle = 1$$ and $$\langle u_1| v_2 \rangle = \langle v_1| v_2 \rangle \neq 0 .$$

Also from a conceptual perspective, the two problems look rather different to me. Gram-Schmidt generates an orthogonal basis that spans the same subspace (vectors whose inner-product with themselves is identity matrix), while what I am looking for are vectors whose inner product with the original vectors is the identity matrix. The $$\{q_k\}$$ are likely not orthonormal themselves in general.

I am probably missing something really simple (physicist here, please be gentle...). Any help would be appreciated. I am not clear under what conditions the required set of vectors can be constructed, so assume linear independence or other properties of $$\{v_k\}$$ where necessary.

Also it is acceptable if the $$\{q_k\}$$ lie outside the span of $$\{v_k\}$$ (or if the vector space and inner product have to suitably be extended for $$\{q_k\}$$ to exist). E.g. if $$\{v_k\}$$ are functions $$\{v_k(r)\}$$and the inner product is the $$l^2$$-Norm, the functions $$\{q_k\}$$ do not have to be linear combinations of $$\{v_k\}$$. In this sense, we are essentially looking for the functions which invert the matrix of the original vectors.

4 Answers

Let $$q_i = \sum_{j=1}^n \beta_{ij}v_j$$, we want it to satisfy

$$\langle q_i, v_j\rangle= \delta_{ij}$$

$$\langle \sum_{k=1}^n \beta_{ik}v_k, v_j\rangle= \delta_{ij}$$

$$\sum_{k=1}^n \beta_{ik}\langle v_k, v_j\rangle= \delta_{ij}$$

This is a linear system of equations.

That is if we define a matrix $$A$$ such that the $$(i,j)$$-th entry is $$\langle v_i, v_j\rangle$$. If $$A$$ is invertible, then $$\beta_{ij}$$ is the $$(i,j)$$-th entry of $$A^{-1}$$.

Upon knowing $$\beta_{ij}$$, we can now solve for $$q$$.

If $$\{ v_1, \ldots, v_n\}$$ is not linearly independent, then no such $$q$$ exists.

WLOG, if $$v_1 = \sum_{k=2}^n c_k v_k$$, suppose $$q_1$$ exists, then we have

$$1=\langle v_1, q_1\rangle = \sum_{k=2}^n c_k \langle v_k, q_1 \rangle=0$$

we get a contradiction.

Now, suppse $$\{v_1, \ldots, v_d\}$$ form a basis where we pick $$v_{n+1}, \ldots, v_d$$ to be orthonormal and orthogonal to the first $$n$$ vectors.

Now, let $$q_i = \sum_{j=1}^d \beta_{ij}v_j$$,

$$\langle \sum_{k=1}^d \beta_{ik}v_k, v_j\rangle= \delta_{ij}$$

$$\sum_{k=1}^d \beta_{ik}\langle v_k, v_j\rangle= \delta_{ij}$$

which reduces to

$$\sum_{k=1}^n \beta_{ik}\langle v_k, v_j\rangle= \delta_{ij}$$

which is the previous case.

• Thanks! This is useful, but I am looking for the more general case where 1) A may not be invertible. 2) The q may not be a linear superposition of the v in the first place. (see last paragraph of the question). Dec 15, 2021 at 22:18
• Can anything be said about that case? Maybe I need to clarify my question further. Dec 15, 2021 at 22:20

$$\langle q_i|v_j\rangle=0$$ for $$i\neq j$$ implies $$\langle q_i|w\rangle=0$$ for any $$w$$ that is a linear combination of the $$v_j$$ with $$j\neq i$$. In particular, $$\langle q_i|v_j\rangle=\delta_{ij}$$ for all $$i$$ and $$j$$ implies no $$v_i$$ is a linear combination of $$v_j$$ with $$i\neq j$$, i.e. that $$\{v_k\}$$ is a linearly independent set.

The Gram--Schmidt procedure takes as input a vector $$v$$ and a finite set $$\{u_i\}$$ of vectors satisfying $$\langle u_i|u_j\rangle=0$$ if $$i\neq j$$ and $$0$$ or $$1$$ when $$i=j$$, its output are the numbers $$\langle v|u_i\rangle$$, the normalization $$u=w/\|w\|$$ of the difference $$w=v-\sum_i\langle v|u_i\rangle u_i$$ (unless $$w=0$$, in which case set $$u=0$$), and the number $$\langle v|u\rangle$$.

Iterating the Gram--Schmidt process on the sequence of vectors $$v_1,\dots,v_n$$ results in a sequence vectors $$u_1,\dots,u_n$$ such that $$\langle u_i|u_j\rangle=0$$ for $$i\neq j$$, $$\langle u_i|u_i\rangle$$ is $$0$$ or $$1$$, and $$R=(r_{ij})_{i,j}=\langle u_i|v_j\rangle$$ an upper triangular matrix, hence such that $$v_j=\sum_{i=1}^jr_{ij}u_i$$.

Note that $$u_k=0$$ (equivalently $$r_{kk}=0$$) if and only if $$v_k$$ is a linear combination of the vectors before it. This suggests weakening the condition $$\langle q_i|v_j\rangle=\delta_{ij}$$ for the desired set $$\{q_k\}$$ to $$\langle q_i|v_j\rangle=0$$ if $$i\neq j$$, $$q_k=0$$ if $$v_k$$ is a linear combination of the vectors before it, and $$\langle q_k|v_k\rangle=1$$ otherwise.

This can be achieved as follows. First, set $$q_k=0$$ if $$u_k=0$$. Then, assuming we have found $$q_{k+1},\dots,q_n$$, set $$q_k=r_{kk}^{-1}(u_k-\sum_{j=k+1}^nr_{kj}q_j)$$. This works because we get $$\langle q_k|v_j\rangle=r_{kk}^{-1}(r_{kj}-r_{kj})=0$$ if $$j>k$$ and $$\langle q_k|v_k\rangle=r_{kk}^{-1}r_{kk}=1$$, and $$\langle q_k|v_j\rangle=0$$ if $$j.

• +1, I like this approach, since it seems to provide a direct algorithm even for the general case. I wonder if this can be implemented when the v_i are functions in L^2? I think Gram-Schmidt works straightforwardly there and yields Q, but I am not sure how to obtain R in that case. Dec 17, 2021 at 12:46
• @Wolpertinger I described how Gram-Schmidt computes $R$, and also how to use $R$ to recursively obtain the vectors you desire (plus what to do in case the set of vectors are linearly dependent) Dec 18, 2021 at 1:16

As has already been stated the $$v_i$$'s need to be linearly independent, or in other words $$\{v_i\}$$ is a basis for $$V=\mathrm{span}\{v_i\}$$. Then $$\{q_i\}$$ is the dual basis, i.e. $$\{\langle q_i | - \rangle\}$$ is a basis for $$V^*$$. This always exists, and we can choose the $$q_i$$'s such that they lie in $$V$$, in which case they will be linear combinations of the $$v_i$$'s. However, we can also add whatever we like to the $$q_i$$'s as long as what we are adding lies in the orthogonal complement to $$V$$, and in this case we can make it so that the $$q_i$$'s don't lie in $$V$$.

In the real finite $$n$$ dimensional case, the equation $$\left = \delta_{ij},$$ for all $$1\leq i,j\leq n,$$ means, in matrix notation, that $$Q^{T} V = I_n.$$ Taking the determinant of both sides, this means that $$\text{det}(V) \text{det}(Q) = 1.$$ Implying that both matrices, $$V$$ and $$Q$$, are invertible. This means that, there is no way of finding a solution for your problem if V is not invertible. On the other hand, if it's possible we have \begin{align}V^{-1} = Q^{T} V V^{-1} = Q^{T}.\end{align} Basically, you just need to apply any method for inverting $$V$$ to get $$Q.$$

Using the QR method on the matrix $$V$$ would have some success, since this would give matrices $$\hat{Q}$$ and $$R$$ such that $$V=\hat{Q}R,$$ which implies $$\hat{Q}^{T} V = R.$$ Now, you will only need to solve $$n$$ linear systems $$R x_i=\hat{Q}^{T} e_i,$$ being $$e_i$$ the $$i$$-th element of the standard basis, to get your desired $$Q.$$ Just to clarify, your matrix $$Q$$ is the transpose of the matrix $$X=[x_1, x_2,\cdots, x_n].$$ This is good because solving upper triangular systems is much easier computationally than directly inverting a $$V$$.

If you really need to find all possible solutions for $$Q$$ whenever $$V$$ is an arbitrary matrix, there is yet a good way of finding it using the thin QR decomposition. Let us say that $$V=\hat{Q}R,$$ where $$\hat{Q}$$ and $$R$$ are given by the QR algorithm, with $$\hat{Q}$$ tall and only satisfying $$\hat{Q}^{T} \hat{Q} = I$$. Since it's requited that $$Q^{T}V = I$$, for some $$Q$$, it implies that $$V$$ has left inverse, which is equivalent to saying that $$V$$ is injective (If $$Q^{T} V = I$$, we have that $$x=0$$ is the only solution for $$Vx=0$$ by multiplying both sides by $$Q^{T}$$). This means that if $$V$$ is not injective, the problem would not have any solution. Being $$V=\hat{Q}R$$, with $$\hat{Q}^{T} \hat{Q} = I,$$ we have that $$R$$ is injective as well (if $$Rx=0,$$ then $$Vx=0$$ and $$x=0$$). Hence, the linear system $$x_i^{T} R = e_i^{T}\tag{*}$$ have at least one solution for each $$1 \leq i\leq n$$, since the columns of $$R$$ are linearly independent. This linear system is equivalent to a lower triangular system $$R^{T} x_i = e_i\tag{**},$$ which is easy to solve computationally. Thus, let us say that $$X=[x_1, x_2,\cdots, x_n]$$ a matrix which solves the linear system $$(*)$$ associated with its indexes $$i$$, i.e., $$X^{T} R = I$$. Hence, your matrix $$Q$$ any of the matrices $$Q=\hat{Q} X,$$ since by $$(**)$$ and the QR decomposition, $$(\hat{Q}X)^{T} V =X^{T} \hat{Q}^{T} V = X^{T} R = I.$$