2-norm vs operator norm

I have read that we define the "2-norm" of a matrix as

$$\max_i \,{|\sigma_i|},$$

which I have also heard called the "operator norm" (here $\sigma_i$ are the singular values).

Also we have the norms

$$\|A\| = \left( \sum_{i,j}|a_{ij}|^q \right)^{1/q}$$

for every $q\geq 1$. Do we refer to these as $\|A\|_q$? (For $q=2$, I have heard this referred to as the "Frobenius norm".) If we do refer to them as $\|A\|_q$, then how can we reconcile the two meanings of the term "two-norm"?

Subquestion: How can we bound the values of $\|A\|$ for $q=1$ and $q=2$ in terms of each other?

I think I understand your question - typically $\|A\|_2$ has two definitions $$ \|A\|_2 = \sqrt{\text{largest eigen value of } A^{\ast}A} $$ and $$ \|A\|^{\prime}_2 = \sup_{\|x\|_2 = 1}\|Ax\|_2 $$ Note that $B = A^{\ast}A$ is a symmetric, positive matrix ($\langle Bx,x \rangle \geq 0$), and hence it can be diagonalized, and its eigen values are non-negative. Write them as $$ \lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n \geq 0 $$ and consider an orthonormal basis $\{u_1, u_2, \ldots, u_n\}$ such that $$ Bu_i = \lambda_i u_i $$ For any $x \in \mathbb{R}^n$, write $x = \sum \alpha_i u_i$, then $$ \|x\|_2 = 1 \Leftrightarrow \sum_{i=1}^n \alpha_i^2 = 1 $$ So consider $$ \|Ax\|^2_2 = \langle Ax,Ax\rangle = \langle A^{\ast}Ax,x\rangle = \sum_{i=1}^n \lambda_i \alpha_i^2 $$ Hence, it follows that $$ \|Ax\|^2_2 \leq \lambda_1 $$ and hence $\|A\|^{\prime}_2 \leq \sqrt{\lambda_1} = \|A\|_2$

The other inequality is obvious - can you see that?

The operator norm of a matrix depends on the norm that you are putting on the vector space on which it acts. So for example if the matrices we consider are in $M_n(\mathbb{R})$ then they are acting on $\mathbb{R}^n$. Given a norm $\| \cdot \|_\alpha$ on $\mathbb{R}^n$ we can create an associated norm (operator norm associated to $\alpha$) by defining

$\|A\|_{(\alpha)}=\sup_{v\neq0}\frac{\|Av\|_\alpha}{\|v\|_\alpha}$.

In the case that we are using the usual euclidean 2-norm for $\mathbb{R}^n$ then the associated $\|\cdot\|_{(2)}$ is what you describe above.

However, we also know that $M_n(\mathbb{R})$ is a vector space isomorphic to $\mathbb{R}^{n^2}$ and so we can put a norm on it this way. These are the $\|A\|_q$ norms that you mention.

In particular $\|A\|_2=\left(\sum|a_{ij}|^2\right)^{\frac{1}{2}}\neq \|A\|_{(2)}$ in general.

Take for example $A=\left(\begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array}\right)$

Then $\|A\|_{(2)}=2$ and $\|A\|_2=\sqrt{5}$

Finally just like any finite dimensional space we have $\|A\|_1\geq \|A\|_2$. Further for finite dimensional spaces all norms give the same topology. This implies that for any two norms and any $A$ in the space there are constants $k_1, k_2>0$ such that $\|A\|_\alpha\geq k_1\|A\|_\beta\geq k_2\|A\|_\alpha$.

Thus there is some constant such that $\|A\|_2\geq k\|A\|_1$ but I don't know what it is off the top of my head. (and it should depend on $n$...maybe $\sqrt{n}$?)

The operator norm is a matrix/operator norm associated with a vector norm. It is defined as

$||A||_{\text{OP}} = \text{sup}_{x \neq 0} \frac{|A x|_n}{|x|}$

and different for each vector norm. In case of the Euclidian norm $|x|_2$ the operator norm is equivalent to the 2-matrix norm (the maximum singular value, as you already stated). So every vector norm has an associated operator norm, for which sometimes simplified expressions as exist.

The Frobenius norm (i.e. the sum of singular values) is a matrix norm (it fulfills the norm axioms), but not an operator norm, since no vector norm exists so that the above definition for the operator norm matches the Frobenius norm.

As far as I know the "q-matrix norms" as you define them (I have never seen these before, and I am also not sure if these fulfill the norm axioms) do not match the q-vector norms as corresponding operator norm in the general case (this is more complicated, I think).