In today's post we will continue our discussion on matrix factorization. We reviewed the method of steepest descent earlier. If we carefully note the iteration step, we were computing the cost of steepest descent with two matrix vector products - one to compute the cost of the current residual and another to compute the step length. We can eliminate one because we can write the equation in terms of the residual and not in terms of the steps. And although we have to compute the starting residual, each subsequent iteration depends only on the previous value. However the disadvantage with this translation is that we lose the feedback from the value of the current step.
At this stage it's probably helpful to review eigenvector. An eigenvector is a non-zero vector that does not rotate when B is applied to it (except perhaps to point in precisely the opposite direction). Since there is scaling and not skewing, we can take the effect of eigenvector as some scalar constant applied to B. This scalar constant denoted by Lambda is called the eigenvalue of B.
As we will see, this is now relevant to our iterations. In each iteration, we depend on applying B to a vector over and over again which either grows it or shrinks it as we proceed along the search line. In particular if we use an eigenvalue of -0.5, the vector converges to zero which we found useful in our zigzag path.
Moreover, if B is symmetric, then there exists a set of n linearly independent eigenvectors of B, denoted by v1, v2, .. vn. This set is not unique and each of them has a corresponding eigenvalue.
Note that the vector applied to B need not be an eigenvector. But we can take a set of n eigenvectors to form the basis and any n-dimensional vector can be expressed as a linear combination of these eigenvectors. If B were to be unsymmetric, then finding a set of n independent eigenvectors is difficult. These matrices are known as defective and we won't speculate why they are called so.  The eigenvalues of a positive-definite matrix are all positive.

#codingexercise
Given a symmetric matrix of increasing numbers from left to right and top to bottom, find the presence of a number
// there are many ways, i just want to find something easy
bool Exists ( int[,] matrix, int number)
{
  // assuming parameter validation
  // we go row wise and do a binary chop
  for (int row = 0; row < matrix.GetLength(0); row++)
  {
       If (BinaryChop(matrix, row, number)) return true;
  }
 return false;
}


bool BinaryChop(int[,] matrix, int row,  int number)
{
  int start = 0;
  int end = matrix.GetLength(0);

  while (start < end)
  {
       Int mid = checked ( (start + end) / 2);
       if (matrix[row, mid] == number) return true;
       if (matrix[row, mid] < number)
             start = mid + 1
       else
             end = mid  - 1
  }
  if (matrix[row, start] == number) return true;
  if (matrix[row, end] == number) return true;
 return false;
}