An upper triangular matrix U has the property that u ij = 0 whenever i > j; that

Question

An upper triangular matrix U has the property that uij = 0 whenever i > j; that is, the entire “lower triangle” of U, consisting of all entries below the main diagonal, must be zero. Examine the matrix A produced by the script gausselim below. Why are some subdiagonal entries nonzero?

% gausselim - script that performs Gaussian elimination on a random 40-by-40 % matrix

m=40;

n=40;

% generate random matrix

A=rand(m,n);

% display it

disp(’Before elimination:’)

disp(A)

for j=1:n-1

     % use elementary row operations to zero all elements in column j below

     % the diagonal

     for i=j+1:m

          mult=A(i,j)/A(j,j);

          % subtract mult * row j from row i

          for k=j:n

               A(i,k)=A(i,k)-mult*A(j,k);

          end

          % equivalent code:

         %A(i,j:n)=A(i,j:n)-mult*A(j,j:n);

         end
end

% display updated matrix

disp(’After elimination:’)

disp(A)

Explanation / Answer

Given A is an m×n matrix.

Matrix A can be a diagonal matrix if the only nonzero entries of A lie on the main diagonal. That is, A is a diagonal matrix if aij = 0 whenever i > j.

Now we can say that matrix A is upper triangular if aij = 0 whenever i > j. That is, all nonzero entries of A are confined to the “upper triangle” of A, which consists of all entries on or “above” the main diagonal.

The above code(script) shows a randomly generated matrix A, and to obtain an upper triangular matrix, Gaussian elimination on A was perfomed, and then shows the final result.

Here we can see that the outermost loop (with loop variable j) executes n 1 times, where the matrix A is m × n, and the next innermost loop (with loop variable j) executes mj times as the variable starts from the value of j+1. Also, the innermost loop, with loop variable k, executes n j + 1 times.

Lastly we can see the statement A(i,j:n) = A(i,j:n) - mult*A(j,j:n).

This statement can also be used instead of the innermost for loop that begins with for k=j:n. Because each iteration of this loop does not depend on the result of previous iterations. So we can see in the aboce code that the relevant portion (columns j through n) of the jth row of A, scaled by mult, can be subtracted from the same portion of the ith row of A in a single operation.

Alternatley, we can conclude that this statement is an implicit for loop, because it must still be carried out through an iteration, but that iteration is implied by the range of indices j:n.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.