alephone

Here is the basic idea of differential privacy in its simplest form.

Suppose that A is a eps-DP algorithm and X1, X2 are two datasets differing by a single point. Recall that for small eps, exp(eps) is roughly (1+eps) and exp(-eps) is roughly (1-eps), so eps-DP yields the guarantee that (roughly speaking), for all subsets S,

    (1-eps) * Pr{ A(X2) \in S } <= Pr{ A(X1) \in S } <= (1+eps) * Pr{ A(X2) \in S }. 

Intuitively speaking, the output distribution of A on X1 and X2 looks roughly the same, only differing by a factor (1 +/- eps), with a fudge factor eps that the user gets to control. Note that this is a very strong notion of stability of an algorithm.

"square matrices have as many eigenvectors as they have linearly independent dimensions; i.e. a 2 x 2 matrix would have two eigenvectors, a 3 x 3 matrix three, and an n x n matrix would have n eigenvectors, each one representing its line of action in one dimension."

This is not quite right. First of all, if v is an eigenvector of A, then a*v for any non-zero a is also an eigenvector of A, so it makes no sense to say "there are n eigenvectors". Perhaps you meant to say n linearly independent eigenvectors?

But this is also not correct. An n x n matrix does not necessarily have to have n linearly independent eigenvectors; consider for instance A = [1, 1; 0, 1], which has dim N(A - I) = 1 (hence 1 linearly independent eigenvector). Basically, not every matrix is diagonalizable. This example also shows that rank(A) is also not necessarily equal to the number of linearly independent eigenvectors (is that what you meant by linearly independent dimensions?).

A more correct statement would be to say every symmetric matrix has n linearly independent eigenvectors (and its eigenvectors can be chosen to form an orthonormal basis for R^n).