2

I have the following matrix : $$ A= \begin{bmatrix} \sum_i w_i^0 & \sum_i w_i & \sum_i w_i^2 \\ \sum_i w_i & \sum_i w_i^2 & \sum_i w_i^3 \\ \sum_i w_i^2 & \sum_i w_i^3 & \sum_i w_i^4 \\ \end{bmatrix} $$ where the sum is finite, say it is $i=1,2,...,5$ and $w_i>0$. I want to prove that every linear system $Ax=b$ has a unique solution.

I have tried to prove that : 1) $ x^t Ax>0$, 2) $det(A)>0$ , 3) The pivots appeared to the Gaussian Elimination are positive. I failed to all of these ways because the expressions are not easy to manipulate. I don't remember why I tried to prove that the matrix A is Positive Definite maybe there is a simpler way to prove that the matrix is nonsingular.

So I appreciate if any of you would give me some advice. Thanks in advance.

Andreas
  • 15,175
chaviaras michalis
  • 634
  • Your goal is to show that $A$ has full rank. However, depending on the values of $w_1, w_2,\ldots$ this may not be true. For example, if each sum is over $i = 1,\ldots,5$ and $w_i = 1$, then $A$ has only rank 1. What more can you tell us about $w_i$? – K. Miller Jan 11 '18 at 12:41
  • @K.Miller I think we should rather have $A_{11} =n$ (if the OP agrees) or we should in the first place set $n=5$ for the whole problem (a particular case of the former). – Andreas Jan 11 '18 at 12:53
  • @K.Miller The problem arose at an optimization problem of a cost function, w_i = e^{2x_i+y_i} , so it is difficult to say something more. – chaviaras michalis Jan 11 '18 at 14:30
  • The above matrix came up from another question I posted. https://math.stackexchange.com/questions/2416199/minimizing-a-function-cost-function-of-3-variables So I think it's difficult for the above matrix to be singular. – chaviaras michalis Jan 11 '18 at 14:37
  • If you can prove that this matrix is the Hessian of a convex function, then you have proven that it is positive semidefinite. Then you only need prove that it is nonsingular, which presumably is simpler. But I agree with @K.Miller that it can be singular. – Michael Grant Jan 11 '18 at 16:07
  • By the way are you sure you can't replace $5$ with $\sum_i w_i^0$? It seems to me the power structure here matters. – Michael Grant Jan 11 '18 at 16:10
  • @MichaelGrant You can because you have $5=n=\sum_{i=0}^{i=5}w_i ^0$ – chaviaras michalis Jan 11 '18 at 16:21
  • @MichaelGrant Yes you are right. – chaviaras michalis Jan 11 '18 at 16:25
  • @K.Miller You are right. There is $w_i$ that makes the A singular – chaviaras michalis Jan 11 '18 at 16:26
  • Thank you all guys !!! – chaviaras michalis Jan 12 '18 at 08:28

1 Answers1

4

I'm going to assume that the $(1,1)$ term can indeed be written as $\sum_i w_i^0$, not fixed at 5. If that's the case, then your matrix becomes

$$\begin{aligned} A &= \sum_i \begin{bmatrix} 1 \\ w_i \\ ... \\ w_i^{n-1} \end{bmatrix} \begin{bmatrix} 1 & w_i & ... & w_i^{n-1} \end{bmatrix}\\& = \begin{bmatrix} 1 & 1 & \dots & 1 \\ w_0 & w_1 & \dots & w_m \\ \vdots & \ \vdots & \ddots & \vdots \\ w_0^{n-1} & w_1^{n-1} & \dots & w_m^{n-1} \end{bmatrix} \begin{bmatrix} 1 & 1 & \dots & 1 \\ w_0 & w_1 & \dots & w_m \\ \vdots & \ \vdots & \ddots & \vdots \\ w_0^{n-1} & w_1^{n-1} & \dots & w_m^{n-1} \end{bmatrix}^T\triangleq B^TB\end{aligned}$$ So $A$ is definitely positively semidefinite, since it has a square root. The rank of $A$ is equal to the rank of $B$, which is a Vandermonde matrix. If $m\leq n$, then the rank is $m$ if and only if if the $w_i$ values are distinct. So it is not positive definite for all $w_i>0$, which means that the convex function involved is not strictly convex, just convex.

Michael Grant
  • 19,450