1
$\begingroup$

I would like to solve the following linear system of equations, represented by this matrix with $n-1$ rows and $n$ columns:

$$\left(\begin{array}{rrrr|r} 2 & 1 & \cdots & 1 & 1 \\ 1 & 2 & \cdots & 1 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 1 & \cdots & 2 & 1 \end{array}\right)$$

i.e. the number in cell $ij$ is $1+\delta_{ij}$ where $\delta_{ij}$ is the Kronecker Delta.

I know one solution to the system of linear equations is that all of the variables is equal to $\frac1{n+1}$. However, it is possible that there are infinitely many solutions to the system. Usually I would figure out if the vectors in this system are linearly dependent, but I'm not sure how to do this if the number of vectors are unknown.

Note: I have verified using Numpy that for $n\leq 1000$ there is only 1 solution.


Context

I was trying to figure out how to solve this problem I was thinking about:

Suppose you have an $n$-dimensional box, with the dimensions summing to $1$ and are all positive. What should the side lengths be to maximize the "volume" of the box?

Suppose we label the box's dimensions $x_1, x_2, \cdots, x_n$. We know $x_n=1-x_i-x_2-\cdots-x_{n-1}$. We can think of the volume as a function of $x_1, x_2, x_3, x_4\cdots x_{n-1}$.

Now the volume of the box is

$$\prod^n_ix_i=\left(1-\sum^{n-1}_jx_j\right)\prod^{n-1}_ix_i=\left(1-\sum^{(n-1)/i}_jx_j-x_i\right)\prod^{n-1}_ix_i=\left(x_i-x_i\sum^{(n-1)/i}_jx_j-x^2_i\right)\prod_k^{(n-1)/i}x_k$$

Where $\sum^{(n-1)/i}_jx_j$ is supposed to mean $x_1+x_2+\cdots+x_{i-1}+x_{i+j}+\cdots+x_{n-1}=\sum^{n-1}_jx_j-x_i$ (I'm not sure what the correct notation is). I gpt the final result by taking the $x_i$ factor out of the product.

Now the partial derivative of the volume with respect to $x_i$ is:

$$\frac{\partial x_i}{\partial V}=\left(1-\sum^{(n-1)/i}_jx_j-2x_i\right)\prod_k^{(n-1)/i}x_k$$

To get a maximum, we need to find $x_1, x_2, \cdots, x_{n-1}$ such that moving any one of the variables in any direction by an infinitesimal amount would not increase the volume, i.e. the partial derivative with respect to each of these variables is $0$. That means we need to find a point where $\frac{\partial x_i}{\partial V}=0$ for all $i$.

Since all of the dimensions are positive, that means $\prod_k^{(n-1)/i}x_k$ is positive, and to get the result we want

$$1-\sum^{(n-1)/i}_jx_j-2x_i=0$$.

We can rewrite this as

$$\sum^{(n-1)/i}_jx_j+2x_i=\sum^{n-1}_jx_j+x_i=1$$

Iterating $i$ from $0$ to $n-1$, I got the equations above.

$\endgroup$
1
$\begingroup$

The square matrix on the left is always invertible by the Sherman–Morrison formula; it can be written as $I_{n-1}+\mathbf1_{n-1}\mathbf1_{n-1}^T$, where $\mathbf1_k$ is a length-$k$ vector of ones, and then the formula says that since $1+\mathbf1_{n-1}^TI_{n-1}\mathbf1_{n-1}=1+n-1=n\ne0$, the square matrix is invertible. Thus the linear system always has a unique solution.

$\endgroup$
0
$\begingroup$

The coefficient matrix is $I+ee^T$ with $I$ the identity matrix and $e$ the vector whose elements are all $1$. The eigenvalues of $ee^T$ are $0$ (with multiplicity $n-1)$ and $n$ (with multiplicity $1$), and by adding the identity matrix the eigenvalues become $1$ and $n+1$. So the coefficient matrix is invertible.

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