How can the value of r that minimizes the norm of a square matrix A be found?

[Chris L T521]

Thanks to those who participated in last week's POTW. Here's this week's problem!

-----

Problem: The norm of a $m\times n$ matrix $A=[a_{ij}]$ is given by the formula

\[\|A\| = \sqrt{\sum_{i=1}^m\sum_{j=1}^na_{ij}^2}.\]

For an $n\times n$ square matrix $A$, show that the value of $r$ that minimizes $\|A-rI\|^2$ is $r=\text{tr}\,(A)/n$, where $\text{tr}\,(A)$ is the trace of $A$ (i.e. the sum of the main diagonal elements of $A$).

-----

 

[Chris L T521]

The following members answered the question correctly: Sudharaka, PaulRS, Opalg, and Bacterius.

There were two different ways of going about this problem. Sudharaka and Bacterius approached the problem the way I did, whereas PaulRS and Opalg used inner product spaces, which I think is more clever!

Here's Bacterius' solution:

Spoiler

For a square matrix $A$ of dimension $n \times n$, the squared norm is:

$\displaystyle ||A||^2 = \sum_{i = 1}^{n} \sum_{j = 1}^{n} a^2_{ij}$

For a square matrix $A - rI$ for some real $r$, $I$ being the identity matrix of same dimensions as $A$, we have:

$\displaystyle ||A - rI||^2 = \sum_{i = 1}^{n} \sum_{j = 1}^{n} (a_{ij} - rI_{ij} )^2$

Clearly the subtraction of $rI$ only affects the diagonal entries of $A$, so we have:

$\displaystyle ||A - rI||^2 = c + \sum_{i = 1}^{n} (a_{ii} - rI_{ii} )^2 = c + \sum_{i = 1}^{n} (a_{ii} - r )^2$

For some constant $c$ solely dependent on $A$. We want to minimize the following with respect to $r$:

$\displaystyle ||A - rI||^2= c + \sum_{i = 1}^{n} (a_{ii} - r )^2$

So we wish to solve $\displaystyle \frac{d}{dr} ||A - rI||^2 = 0$

$\displaystyle \frac{d}{dr} ||A - rI||^2 = \frac{d}{dr} \left [ c + \sum_{i = 1}^{n} (a_{ii} - r )^2 \right ] = \sum_{i = 1}^{n} (2r - 2a_{ii}) = 2 \sum_{i = 1}^{n} (r - a_{ii})= 2 \left [ \sum_{i = 1}^n r - \sum_{i = 1}^n a_{ii} \right ] = 2 \left ( rn - \mathrm{tr} (A) \right ) = 0$

Solving for $r$:

$\displaystyle 2 \left ( rn - \mathrm{tr} (A) \right ) = 0 ~~~ \implies ~~~ r = \frac{\mathrm{tr} (A)}{n}$

Because the function being minimized is quadratic in $r$ with a positive coefficient, the only solution to the derivative function must be a minimum. Therefore:

$\displaystyle ||A - rI||^2 ~~~$ is minimized by $\displaystyle ~~~ r = \frac{\mathrm{tr} (A)}{n}$

$\mathbb{QED}$

Here's PaulRS's solution:

Spoiler

Let us define an inner product for the $n\times n$ matrices: $ \left \langle A, B \right \rangle= \displaystyle\sum_{i=1}^n \sum_{j=1}^n [A]_{i,j} \cdot _{i,j}$ . The given norm is, in fact, the norm derived from this inner-product.

The key now is to note that the subspace generated by $\{I\}$ is $\{ r \cdot I : r \in {\mathbb R} \}$. Thus if we want $r\in {\mathbb R}$ that minimizes $ \| A - r \cdot I \| ^2$, that is exactly the $r$ that makes $r\cdot I$ the projection of $A$ onto the subspace generated by $\{I\}$.Since $\{I\}$ is already an orthogonal base, the projection is $\displaystyle\frac{\left \langle A , I \right \rangle}{\left \langle I, I \right \rangle} \cdot I= \frac{\text{tr}(A)}{n} \cdot I $ , because $\left \langle A, I \right \rangle = \text{tr} (A)$ and $\left \langle I, I \right \rangle = n$.Thus indeed: $r = \displaystyle\frac{\text{tr}(A)}{n} $.