[timeforchg]

A. Now consider the product P = ST are S, where S is an upper triangular matrix having 0 everywhere except 1 on the main diagonal and ?1 on the first super diagonal. Write the exact form of P.

B. A new algorithm is now proposed to solve the linear system Rx = b. It is in four steps:
Step A. Let x = Sy to get are Sy = b.
Step B. Multiply both sides of are Sy = b by ST to write ST are Sy = STb = c or Py = c.
Step C. Solve Py = c to obtain why.
Step D. Compute x as x = Sy.
Show the computations performed at each step when the data vector b = [1 1 1 ? 1]T.

[jcaron2]

You seem to have started the problem somewhere in the middle, without its preamble. Is the matrix R special in any way? Is it real? Complex? Symmetric? Hermitian? Upper Diagonal? Etc. If it's just a general n-by-n matrix I don't see how P has any special form. Based on part B of the question, it's clear that P is supposed to have some easily invertable form.

For clarification for anybody else reading this, I'm pretty sure wherever you see "are", you're supposed to put in R, the T is supposed to be superscripted (meaning that ST is S-transpose), and the ?1 on the superdiagonal is actually -1.

[P]=[S^T][R][S]

[timeforchg]

Hi, Below are the full question. I have already done part A to E, stuck at F & G. Thanks.

1. Consider a sequence of real-numbers r1, r2, …, rN. Using these we create an
(N × N)
square matrix R such that
(I, j)-th element of R = rk, where k = min(I, j), I = 1, 2, …, N; j = 1, 2, …, N.

A. Write the matrix R in terms of its elements. Clearly, show at least the top 4 × 4 part and all the elements on the four corners.

B. Is this a symmetric matrix?

C. Carry out appropriate EROs to reduce the matrix to its echlon form. Is this echlon form unique?

D. Carry out appropriate EROs to reduce the matrix to its row echlon form. (15 points)

E. Carry out appropriate EROs to reduce the matrix to its reduced row echlon form.

F. Now consider the product P = ST R S, where S is an upper triangular matrix having 0 everywhere except 1 on the main diagonal and –1 on the first super diagonal. Write the exact form of P.

G. A new algorithm is now proposed to solve the linear system Rx = b. It is in four steps:
Step A. Let x = Sy to get R Sy = b.
Step B. Multiply both sides of R Sy = b by ST to write ST R Sy = STb = c or Py = c.
Step C. Solve Py = c to obtain y.
Step D. Compute x as x = Sy.
Show the computations performed at each step when the data vector b = [1 1 1 … 1]T.

[Unknown008]

There are symbols not appearing well... Could you type them by hand, or alternatively explain what each one means?

[timeforchg]

Hi, I have re written the question.

1. Consider a sequence of real-numbers r1, r2, rN. Using these we create an
(N x N)square matrix R such that(I, j)th element of R = rk, where k = min(I, j), I = 1, 2,. N;
j = 1, 2, N.

A. Write the matrix R in terms of its elements. Clearly, show at least the top 4 x 4 part and all the elements on the four corners.

B. Is this a symmetric matrix?

C. Carry out appropriate EROs to reduce the matrix to its echlon form. Is this echlon form unique?

D. Carry out appropriate EROs to reduce the matrix to its row echlon form.

E. Carry out appropriate EROs to reduce the matrix to its reduced row echlon form.

F. Now consider the product P = ST R S, where S is an upper triangular matrix having 0 everywhere except 1 on the main diagonal and -1 on the first super diagonal. Write the exact form of P.

G. A new algorithm is now proposed to solve the linear system Rx = b. It is in four steps:
Step A. Let x = Sy to get R Sy = b.
Step B. Multiply both sides of R Sy = b by ST to write ST R Sy = STb = c or Py = c.
Step C. Solve Py = c to obtain y.
Step D. Compute x as x = Sy.
Show the computations performed at each step when the data vector b = [1 1 1... 1]T.

*T = transpose

[jcaron2]

In that case, P is simply the NxN identity matrix. If you simply carry out the manual matrix multiplication of S' * R (for some reasonable value of N, say 5), you'll quickly see that the result is an upper triangular matrix of all ones:



If we then post-multiply that result by S, you can see that the result is the identity matrix:



This makes your second question (part G) easy. Simply follow the prescribed steps. Before knowing the form of P, the only apparently difficult part was step C, because it involves inverting P. Now that you know that P is simply an identity matrix, step C is trivial. It boils down to y=c. That means that in the end, the algorithm in part G comes down to this:



Note that the product of S with its transpose is an NxN matrix with 2's on the diagonal and -1's on the first superdiagonal and subdiagonal.

Let me know what you get for an answer for x.

[jcaron2]

By the way, if you were to solve the linear equation in part G the brute-force way (i.e. without the algorithm using S), you'd do the following:







But the algorithm presented in part G resulted in:



That tells you that if you did everything correctly:



Sure enough, if you find the inverse of R, you'll find that it's a matrix with 2's on the diagonal and -1's on the first sub- and superdiagonals.

[timeforchg]

Hi Jcaron2,

For Part(F) My answer for P is

P =
[ 1 -1 0 0... 0
-1 2 -1 0... 0
0 -1 2 -1... 0
0 0 -1 2... 0

: : : : :
: : : : :
: : : : :

0 0 0 0 1]


and therefore for my part (G) I get...

x = [ 1 -1 0 0... 0 [ N
0 1 -1 0... 0 N-1
0 0 1 -1... 0 N-2
0 0 0 1... 0 N-3

: : : : : :
: : : : : :

0 0 0 0... 1] 1]

= [ N - (N-1)
N-1-(N-2)
N-2-(N-3)
N-3-(N-4)

:
:

1]

= [ 1
1
1
1

:
:

1]


Is it correct? Please help to verify.
thanks.

[jcaron2]

Hmmm... definitely not the same thing I got. When you write out S, S-transpose, and R, are they the same as what I got above? I only wrote them down for a 5x5 matrix, but it should be pretty obvious what they'd look like for an N x N.

If you get the same answer as me for those matrices, then we'll have to see how you're doing the multiplication.

[timeforchg]

Do you mind sending me your working solution so that I could compare it with mine and see what went wrong.
T

[jcaron2]

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

[timeforchg]

Thanks for the input. Really helped me. Appreciate your time.

[jcaron2]

No problem. Glad to help!