2
$\begingroup$

I wonder how the Big Oh and Little Oh notation works while working with matrices. The wikipedia page doesn't list any matrix results, and so do the sources of this question.

As a remainder:

(D1) $a_n = O(b_n)$ if there exist a $M > 0$ and $N$ such that $|a_n/b_n| < M$ for $n > N$

(D2) $a_n = o(b_n)$ if for any $M > 0$, there exists a $N_M$ such that $|a_n/b_n| < M$ for $n > N$

Consider vector $v_n$ and $w_n$, sequences of matrices ${\bf A}_n$ and ${\bf B}_n$ and $||{\bf A}||$ the sup norm of ${ \bf A}$ and $|{\bf A}|$ the determinant. I assume them commutative as needed. Of course, there is the obvious,

(1) If $||{\bf A}_n|| = O(1),||{\bf B}_n|| = O(1)$ then $|| { \bf A } _n { \bf B }_n || = O(1)$

(2) If $||{\bf A}_n|| = O(1)$, $v_n = O(1)$, and $w_n = O(1)$, then $v_n{\bf A}_n w_n = O(1) $

Both (1) and (2) can be proved easily by taking the max over each element.

(3) I also found out recently that

If $||{\bf A}_n^{-1}|| = O(a_n)$, $a_n \to \infty$, and $||{\bf B}_n|| = o(1)$ , then $||[{ \bf A}_n + { \bf B}_n]^{-1}|| = O(a_n)$

(4) For semidefinite $k\times k$ matrices ${\bf A}_n$, $tr({\bf A}_n) = O(a_n)$ iff $\lambda_{n}^L = O(a_n)$ iff $||{\bf A}_n|| = O(a_n)$, with $\lambda_n^L$ the largest eigenvalue of ${\bf A}_n$. Also, these imply $|{\bf A}_n| = O(a_n^k)$ and, for positive definite matrices, $log(|{\bf A}_n|) = O(a_n)$.

(5?) However, a book I recently read implicitly uses a result that I find dubious,

If $|{\bf A}_n| = O(1)$ and $v_n = O(1)$, then $v'_n{\bf A} v_n = O(1)$

Statement (5) seems very suspicious since for a given determinant you can have a norm arbitrarily large. However, maybe it is somehow true for (semi)-positive definite matrices?

In any case I wonder if someone compiled a list of nice results of the $O(1)$ and $o(1)$ notation for matrices.

$\endgroup$
1
$\begingroup$

If $|A_n|$ is the determinant, (5) is false even for PD matrices. Take simply $$ A = \begin{bmatrix}\frac1\varepsilon & 0\\ 0 & \varepsilon\end{bmatrix}, \quad v = \begin{bmatrix}1\\0\end{bmatrix}. $$

As for a list of big-O results, I don't know of one, and I think it would be too big to be remotely useful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.