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.
 A: 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.
A: $\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<k$.
A: In the real finite $n$ dimensional case, the equation $$\left<v_i | q_j\right> = \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.$
A: 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$.
