1
$\begingroup$

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.

$\endgroup$

4 Answers 4

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$ Dec 15, 2021 at 22:18
  • $\begingroup$ Can anything be said about that case? Maybe I need to clarify my question further. $\endgroup$ Dec 15, 2021 at 22:20
1
+50
$\begingroup$

$\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$.

$\endgroup$
2
  • $\begingroup$ +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. $\endgroup$ Dec 17, 2021 at 12:46
  • $\begingroup$ @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) $\endgroup$ Dec 18, 2021 at 1:16
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.