Skip to content

2.2-exam1-2013-edelman

Quiz 1, 2013 (edelman) · Section 2.2: Elimination Matrices and Inverse Matrices Source: exam1_2.pdf, pp. 48, 53

Problem

5 (15 pts.) An elimination step (a multiple of one row subtracted from another row) may be written in Julia as A[j,:] -= m*A[i,:] where we assume \(i \neq j\). The same row operation in matrix form is expressed in linear algebra by "replace \(A\) with \(EA\)", where \(E\) is the matrix formed from the identity with \(-m\) in the \((j, i)\) entry. If Gauss-Jordan is performed on an \(n\) by \(n\) non-singular matrix \(A\), augmented with \(I\), provide an exact count in terms of \(n\) of the general number of required elimination steps. (Hint: we are counting in units of row operations, not elemental operations; the exact answer has the form \(an^2 + bn + c\).) We want the exact answer and a very short reason why.

Solution In each of the \(n\) columns, we use the pivot to reduce each of the other \(n - 1\) entries to 0. Therefore we use \[ n(n - 1) \] elimination steps: \(n\) columns, each requiring \(n - 1\) row operations (the entries above and below the pivot).

Keywords: Gauss-Jordan, elimination steps, operation count