# Unique coordinates (solutions) in a single Gauss-Seidel iteration

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices (symmetric, positive semi-definite; negative off-diagonal entries, with rows(collumns) summing (in absolute values) to positive diagonal entries; matrix eigenvalue $0$ corresponds to $1_n$ eigenvector of the nullspace), and $x,y\in\mathbb{R}^{n\times 2}$ are vectors with the unknown $x$. The solution has the form $$x_i^{[k+1]} = \left.\left(b_i - \sum_{j=1}^{i-1}a_{ij}x_j^{[k+1]} - \sum_{j=i+1}^{n}a_{ij}x_j^{[k]}\right)\middle/a_{ii}\right.,$$ where $b_i$ is the $i^{th}$ entry of $Ly$. Note that, with Gauss-Seidl, the update of $x_i$ takes effect immediately, i.e., calculation for the following $x_{i+1}$ is based on the new value of $x_i$ that has been computed just before.

Now, suppose an iteration consists of a single update of all $x_i$ in some arbitrary order. In other words, each $x_i$ is considered only once (and is updated only once) in an iteration. My question is: could it be guaranteed that after a single iteration with initial $x^{[0]}=y$, the solution $x^{[1]}$ has all unique coordinates, i.e., there are not two rows of $x^{[1]}$ that are equal?

You could assume that the initial $x^{[0]}=y$ has non-unique coordinates. If the uniqueness cannot be resolved this way, I would appreciate a suggestion on the coordinate traversal order to increase the chance of achieving uniqueness (i.e., no two coordinates take the same value).

• So, I built upon some of HuiZhang's edits, but in the process, I may have inadvertently changed the meaning of the question, because I found your definition of "uniqueness" a bit confusing. Could you look over the edited question to make sure I interpreted correctly your comments on JedBrown's answer? – Geoff Oxberry Mar 28 '12 at 6:44
• @GeoffOxberry Yes, it's an alternative way. Thanks. – usero Mar 28 '12 at 7:17
• Hi, do you have any property of $A$ and $L$. Otherwise, if $A=L=I$ and some rows of $y$ are the same, then you can never get the rows unique by Gauss-Seidel relaxation because $x^{[k]}=y$. – Hui Zhang Mar 28 '12 at 14:16
• @HuiZhang I edited the question (see the property of $A, L$). I apologize for missing this. – usero Mar 28 '12 at 14:38

The order in which you update the new solution has a big impact on the values produced from the initial data to the first approximation. Some updated values will be the same as the jacobi iteration, while others will contain the latest information a la Gauss-Seidel. Given a specific ordering, there may be two values that are the same if the initial vector $x_0$ has non-unique values. But for two different orderings, if the the solution vector is large, and the order of updating the gauss-seidel formula is random, the more unlikely it is that you will produce similar 1st iterations. I'm not sure if there is a proof for that different orderings produce unique 1st iterations, but even if it is possible for them to be non-unique, the probability is very unlikely.

• I think you're right about this. But, perhaps, there might be an ordering devised such that, at the end of the first iteration, one really gets unique solutions. On the other hand, this imposes higher computational time (to determine the ordering). – usero Mar 26 '12 at 19:00

Application of Gauss-Seidel is a nonsingular affine operator (for matrices and orderings in which Gauss-Seidel is convergent), let's call the linear part $G$. That is, with $A = L + D + U$, we have $x_1 = (L+D)^{-1}(b - U x_0) = \tilde b + G x_0$. Without loss of generality, let's take $b = 0$, in which case $\tilde b = (L+D)^{-1} b = 0$, thus $x_1 = G x_0$ with $G = (L+D)^{-1} U$ nonsingular.

If I understand your question, you are asking whether observing $G x_0 = G y_0$ (i.e. identical results after one iteration of Gauss-Seidel) implies that $x_0 = y_0$. Well, $G (x_0 - y_0) = 0$ is only possible if $x_0 - y_0 = 0$ or if $G$ is singular.

Note that Gauss-Seidel may damp some modes very fast so you can get iterates that are very close even though the initial vectors were different.

• I don't think you understood it correctly. Suppose a system $$Ax=Ly$$ is given, with the unknown $x$, and suppose I want to perform a single iteration of GS, where an iteration implies that all $x_i$ (all rows of $X$) are visited once, in some order. Now, given that the initial guess $x_0$ from which I start GS is $x_0=y$, I want to know if there are guarantees that all new $x_i$ (so, rows on the resulting matrix, after the first iteration) are different (there are no coincidences). I hope this clarifies the question. – usero Mar 26 '12 at 19:57
• No, there is no reasonable way to guarantee that. Why would you care whether two entries in the same vector happened to be the same or not? – Jed Brown Mar 26 '12 at 20:01
• Good point. Because it $is$ claimed on some places that the uniqueness is guaranteed. I wanted to prove that, perhaps, under certain visiting order, one might really guarantee uniqueness. – usero Mar 26 '12 at 20:11
• Where is it claimed that uniqueness is guaranteed? This is a very strange definition of unique... – Aron Ahmadia Mar 26 '12 at 20:25
• @usero: Out of curiosity, what do you expect to gain from knowledge of the uniqueness of the first iteration vectors? What application is this for? – Paul Mar 26 '12 at 22:51

This question is ill-posed. Gauss-Seidel is an iterative method for solving a linear system of equations that is guaranteed to converge for certain matrices. If the solution to the linear system of equations contains non-unique values, then Gauss-Seidel will converge to non-unique values. The iteration number and order of applying the updates are irrelevant.

• I think he's refering to the values of the approximated solution after only 1 iteration (the first iteration), not after many iterations. – Paul Mar 26 '12 at 17:26
• I agree that the OP is asking about the first iteration, but all of the classic theory regarding Gauss-Seidel applies to the converged result, which is why I brought it up. – Aron Ahmadia Mar 26 '12 at 17:49
• I'm only interested in a $single$ iteration of Gauss-Seidl, and I'm aware of the convergent solution properties. – usero Mar 26 '12 at 19:00