«

A Cute Identity.

Abstract.

Today I present a cute identity which appeared while explicitly computing the Gram-Schmidt orthogonalization of a base.

Recently, while doing some computations, I stumbled about a very interesting identity, which I do not want to withhold from you all:

Theorem.

Let K be a field and x_1, \dots, x_n \in K such that 1 + \sum_{j=1}^i x_i \neq 0 for all i = 1, \dots, n. Then \displaystyle 1 - \sum_{i=1}^n \frac{x_i}{\Bigl( 1 + \sum_{j=1}^{i-1} x_j \Bigr) \Bigl( 1 + \sum_{j=1}^i x_j \Bigr)} = \frac{1}{1 + \sum_{i=1}^n x_i}.

It is very easy to prove it by induction:

Proof.

For n = 1, the left-hand side equals \displaystyle 1 - \frac{x_1}{( 1 ) ( 1 + x_1 )} = \frac{1 + x_1 - x_1}{1 + x_1} = \frac{1}{1 + x_1}, which equals the right-hand side for n = 1. Hence, the statement is true for n = 1. Now assume that it holds for n. Then
& 1 - \sum_{i=1}^{n+1} \frac{x_i}{\Bigl( 1 + \sum_{j=1}^{i-1} x_j \Bigr) \Bigl( 1 + \sum_{j=1}^i x_j \Bigr)} \\ {}={} & 1 - \sum_{i=1}^n \frac{x_i}{\Bigl( 1 + \sum_{j=1}^{i-1} x_j \Bigr) \Bigl( 1 + \sum_{j=1}^i x_j \Bigr)} \\ {}-{} & \frac{x_{n+1}}{\Bigl( 1 + \sum_{j=1}^n x_j \Bigr) \Bigl( 1 + \sum_{j=1}^{n+1} x_j \Bigr)} \\ {}={} & \frac{1}{1 + \sum_{i=1}^n x_i} - \frac{x_{n+1}}{\Bigl( 1 + \sum_{j=1}^n x_j \Bigr) \Bigl( 1 + \sum_{j=1}^{n+1} x_j \Bigr)} \\ {}={} & \frac{1 + \sum_{j=1}^{n+1} x_j}{\Bigl(1 + \sum_{i=1}^n x_i\Bigr) \Bigl( 1 + \sum_{j=1}^{n+1} x_j \Bigr)} - \frac{x_{n+1}}{\Bigl( 1 + \sum_{j=1}^n x_j \Bigr) \Bigl( 1 + \sum_{j=1}^{n+1} x_j \Bigr)} \\ {}={} & \frac{1 + \sum_{j=1}^n x_j}{\Bigl(1 + \sum_{i=1}^n x_i\Bigr) \Bigl( 1 + \sum_{j=1}^{n+1} x_j \Bigr)} = \frac{1}{1 + \sum_{j=1}^{n+1} x_j}, what we had to show.
□

Yet, I have no idea what this identity should tell me. The left-hand side looks so complicated, there is no indication it should simplify to something like the right-hand side. This identity miraculously appeared when I computed the Gram-Schmidt orthogonalization of the linearly independent system v_i = \lambda_i e_i + e_n, 1 \le i < n, where \lambda_i \in \R \setminus \{ 0 \} and e_1, \dots, e_n is the standard orthonormal base of \R^n. It turns out that one can explicitly describe the Gram-Schmidt orthogonalization, namely it is \hat{v}_1, \dots, \hat{v}_{n-1} with \displaystyle \hat{v}_i = \lambda_i e_i + \frac{1}{1 + \sum_{j=1}^{i-1} \lambda_j^{-2}} \biggl( -\sum_{j=1}^{i-1} \lambda_j^{-1} e_j + e_n \biggr), and the squared norm of \hat{v}_i is given by \displaystyle \langle \hat{v}_i, \hat{v}_i \rangle = \lambda_i^2 \cdot \frac{1 + \sum_{j=1}^i \lambda_j^{-2}}{1 + \sum_{j=1}^{i-1} \lambda_j^{-2}}. This one can also easily show by induction, using the above identity; it appears two times with x_i = \lambda_i^{-2}. Note that the system (v_1, \dots, v_{n-1}) already appeared once in this blog, namely when I tried to find the closest vector in its span to e_n; this was done in this post.

In case you have seen this identity before, let me know. I’m really curious if it has been used somewhere else.

Tags: ,

This entry was posted on saturday, july 30th, 2011 at 12:35 utc and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply