# How to solve a linear system by LinearSolve when the variables are duplicate?

Given that I have a set of equations about varible $x_0,x_1,\cdots,x_n$, which own the following style:

$\left( \begin{array}{cccccccc} \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{6} & \frac{2}{3} & \frac{1}{6} & 0 \\ \end{array} \right) \left( \begin{array}{c} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ \color{red}{x_0} \\ \color{red}{x_1} \\ \color{red}{x_2} \\ \end{array} \right)=\left( \begin{array}{c} (1,1) \\ (2,3) \\ (3,-1) \\ (4,1) \\ (5,0) \\ \end{array} \right)$

Obviously, I cannot solve this linear system by LinearSolve[]. To solve this equation group, I only used the Solve[].

mat=
{{1/6, 2/3, 1/6, 0, 0, 0, 0, 0}, {0, 1/6, 2/3, 1/6, 0, 0, 0, 0},
{0, 0, 1/6, 2/3, 1/6, 0, 0, 0}, {0, 0, 0, 1/6, 2/3, 1/6, 0, 0},
{0, 0, 0, 0, 1/6, 2/3, 1/6, 0}};
eqns = mat.{x0, x1, x2, x3, x4, x0, x1, x2};


$\begin{pmatrix} \frac{x_0}{6}+\frac{2 x_1}{3}+\frac{x_2}{6}\\ \frac{x_1}{6}+\frac{2 x_2}{3}+\frac{x_3}{6}\\ \frac{x_2}{6}+\frac{2 x_3}{3}+\frac{x_4}{6}\\ \frac{x_0}{6}+\frac{x_3}{6}+\frac{2 x_4}{3}\\ \frac{2 x_0}{3}+\frac{x_1}{6}+\frac{x_4}{6} \end{pmatrix}$

yValues = {{1, 1}, {2, 3}, {3, -1}, {4, 1}, {5, 0}};
part1 = {x0, x1, x2, x3, x4} /.
Solve[Thread[eqns == yValues[[All, 1]]], {x0, x1, x2, x3, x4}]
part2 = {x0, x1, x2, x3, x4} /.
Solve[Thread[eqns == yValues[[All, 2]]], {x0, x1, x2, x3, x4}]
res = Transpose[Join[part1, part2]]

 {{75/11, -8/11}, {-9/11, 4/11}, {27/11, 58/11}, {3, -38/11}, {39/11, 28/11}}


### Question

However, the index $n$ for variables $\{x_0,x_1,\cdots,x_n\}$ is very large ($n=100$) in my work. My solution that by Solve[] is very cockamamie. So I would like to know how to deal with this case by the built-in LinearSolve[] efficiently?

• You can partition your x-vector as $(x,y,x)$, where $x=(x_0,x_1,x_2)$ and $y=(x_3,x_4)$, and your matrix mat in a similar way (3x3 block matrix). Multiplying out the blocks and collecting $x$ and $y$ together will give you the linear system of reduced size that you can feed to LinearSolve – sebhofer Oct 23 '15 at 8:16
• Do a fold-over: $$\begin{pmatrix}\frac16&\frac23&\frac16&0&0\\ 0&\frac16&\frac23&\frac16&0\\ 0&0&\frac16&\frac23&\frac16\\ \frac16&0&0&\frac16&\frac23\\ \frac23&\frac16&0&0&\frac16\end{pmatrix} \begin{pmatrix}x_0\\x_1\\x_2\\x_3\\x_4\end{pmatrix} =\begin{pmatrix}(1,1)\\(2,3)\\(3,-1)\\(4,1)\\(5,0)\\\end{pmatrix}$$ Is this part of your closed spline interpolation problem? – J. M.'s technical difficulties Oct 23 '15 at 8:33
• @J.M. Yes, see here – xyz Oct 23 '15 at 8:41
• Maybe I missed something in your question. But once you have the equations, you can find the corresponding matrix by CoefficientArrays[eqns, {x0, x1, x2, x3, x4}][[2]] and then use LinearSolve. – Fred Simons Oct 23 '15 at 8:59
• @FredSimons Yes, your method is right. I have achieved the right result by your method:) – xyz Oct 23 '15 at 9:10

How to fold a "wide" matrix over to enforce "periodic" conditions:

mat = {{1/6, 2/3, 1/6, 0, 0, 0, 0, 0}, {0, 1/6, 2/3, 1/6, 0, 0, 0, 0},
{0, 0, 1/6, 2/3, 1/6, 0, 0, 0}, {0, 0, 0, 1/6, 2/3, 1/6, 0, 0},
{0, 0, 0, 0, 1/6, 2/3, 1/6, 0}};

{m, n} = Dimensions[mat];

LinearSolve[Take[mat, m, m] + PadRight[Take[mat, m, m - n], {m, m}],
{{1, 1}, {2, 3}, {3, -1}, {4, 1}, {5, 0}}]

{{75/11, -8/11}, {-9/11, 4/11}, {27/11, 58/11}, {3, -38/11}, {39/11, 28/11}}

• Is fold-over the "official" name for this operation? – sebhofer Oct 23 '15 at 10:15
• I'm not aware of an official name, but I like the picturesque terminology. :) – J. M.'s technical difficulties Oct 23 '15 at 10:18
• I agree. It was just that you so confidently calling it "fold-over" in your comment made me feel like I should have known that it was actually a thing :-) – sebhofer Oct 23 '15 at 10:29
• J.M. I would like to ask you a question about well-condition. For a square matrix $A$, I can use the formula $cond(A)=||A|||A^{-1}|||$ to calculate the conditional number of matrix $A$. However, I didn't know which value is proper for well-condition. Thanks a lot. – xyz Oct 29 '15 at 2:15
• @Shutao, the idea with conditioning is that the nearer the condition is to $1$, the better the conditioning of the problem (as in the case of orthogonal/unitary matrices). Ill-conditioned systems have large condition numbers, and truly singular systems have infinite condition numbers. – J. M.'s technical difficulties Oct 29 '15 at 2:28
l = 5; s = 3;
(* Solution 1 *)
# + SparseArray[#2, {l, l}] & @@ InternalPartitionRagged[mat\[Transpose], {l, s}];
LinearSolve[%\[Transpose], yValues]

(* Solution 2 *)
Module[{m = #[[;; l]]}, m[[;; s]] += #[[-s ;;]]; m] &[mat\[Transpose]];
LinearSolve[%\[Transpose], yValues]

• Cool, InternalPartitionRagged can be very useful! – sebhofer Oct 23 '15 at 10:10

This script accepts the equations (consistent equations) with the unknowns in any order.

vars = Variables[eqns]