Skip to content

2.1-exam1-2010-fall

Exam 1, 2010 (fall) · Section 2.1: Elimination and Back Substitution Source: exam1_1.pdf, p. 222

Problem

4 (20 pts.) Write an informal computer program to calculate \(xx^Tx\), for any \(n \times 1\) column vector \(x\). The program should only use about \(2n\) operations and no more than about \(2n\) numbers in memory. You can write the program in MATLAB or your favorite language. It is not important that you remember exact syntax, but it is important that your operations are clear and unambiguous.

Solution The naive way to do this is to first multiply \(xx^T\) and then multiply by \(x\). But \(xx^T\) is an \(n \times n\) matrix, so it doesn't meet the requirement of having roughly \(2n\) numbers in memory (or the \(2n\) operations requirement). The point is that matrix multiplication is associative, so we can instead do \(x(x^Tx)\), i.e., calculate \(x^Tx\) which is a single number, and then multiply \(x\) by this number. If the entries of \(x\) are \(x_1, \dots, x_n\), then the final answer would be \[ \begin{bmatrix} cx_1 \\ cx_2 \\ \vdots \\ cx_n \end{bmatrix}, \qquad \text{where } c = x_1^2 + x_2^2 + \cdots + x_n^2. \] So a program that does this should roughly look like this:
c := 0;
for i from 1 to n do c := c + x[i]*x[i];
for i from 1 to n do answer[i] := x[i]*c;
return answer;

Keywords: matrix multiplication, associativity, algorithm, operations count