My full solution is essentially shown in my post above. Let's do it in terms of i's and j's and the definition of the matrix R:
First, the matrix S is given to us outright. So S and S^T are straightforward (and are shown in my post above). S is a matrix with 1's on the diagonal and -1's on the first superdiagonal; S^T is a matrix with 1's on the diagonal and -1's on the first
subdiagonal.
Now to compute S^T * R: Since these are both N-by-N matrices, we do matrix multiplication the normal way where element (i,j) is equal to the sum of the products of each element in the
ith row of S^T and the corresponding element in the
jth column of R.
Because of the form of S^T, there are at most only two non-zero elements in this summation - the element when k=i-1 (in which case S^T(i,k) = -1) and the element when k=i (in which case S^T(i,k) = 1).
Thus the summation works out to:
It's pretty obvious that if j<i, then min(i,j) = min(i-1,j) = j. Hence, [S^T*R](i,j) = j - j = 0 for all j<i. On the other hand if j=i or j>i, then min(i,j) = i and min(i-1,j) = i-1. Hence, [S^T*R](i,j) = i - (i-1) = 1 for all j>=i.
Putting it all together, this makes [S^T*R] an upper triangular matrix of ones, as I said before.
The next step is to multiply [S^T*R] by S to get the matrix P. Again, because of the form of S, there are at most only two non-zero components to the summation for each term in the matrix, and you'll find that the result is a matrix with 1's on the diagonal and 0's everywhere else (i.e. an identity matrix). I trust you can do the work to show this is true?
Given that P is an identity matrix, that means that y=c (i.e. y=S^T*b), as i said before, which means x=S*S^T*b.
Again, this matrix product is straightforward:
The first term in the product, S(i,k), is only non-zero when k=i (in which case it's equal to 1) or k = i+1 (in which case it's equal to -1). Meanwhile, the second term, S^T(k,j) is only non-zero when k=j (in which case it's equal to 1) or k = j-1 (in which case it's equal to -1). Hence, there are only a few combinations of i and j which result in non-zero products: i=j (i.e. the diagonal), i=j-1 (i.e. the first super-diagonal), and i=j+1 (i.e. the first sub-diagonal). In the first case, i=j, we only get non-zero products when k = i = j (in which case it's 1 * 1 = 1) or when k= i+1 = j+1 (in which case it's -1 * -1 = 1). Hence, for i=j, the summation always works out to 1 + 1 = 2,
except for the case of i = j = N (the very bottom right component of the matrix). In this case, the index k can not exceed N; hence there's only one non-zero component to the summation, which therefore works out to only 1. (Note that I forgot to mention that in my previous post. Sorry about that!)
Meanwhile, for the case of i=j-1, the above summation only has one non-zero element which occurs when k=i, in which case S(i,k) = S(i,i) = 1 and S^T(k,j) = S^T(i,i+1) = -1, so the summation comes out to -1. Hence the first super-diagonal is all -1's.
Finally, for the case of i = j+1, the above summation again only has one non-zero element which occurs when k=j, in which case S(i,k) = S(i,i+1) = -1 and S^T(k,j) = S^T(j,j) = 1, so the summation again comes out to -1. Hence the first sub-diagonal is also all -1's.
That means the matrix S * S^T has 2's on the diagonal except for the very bottom right component, which is a 1; and it has -1's on the first super- and sub-diagonals. It is zero everywhere else.
At last, if we multiply this matrix by the vector
b of all ones, the answer
x is a vector whose components are simply the sum of the components of the corresponding row of the S * S^T matrix. Hence