What is the norm of the pre-multiplication by a fixed matrix operator? Let $A \colon= \left(\alpha_{ij} \right)_{m\times n}$ be a given $m \times n$ matrix of complex numbers, and let the operator $T \colon \mathbb{C}^n \to \mathbb{C}^m$ be defined by 
$$T(x) \colon= Ax \ \ \ \mbox{ for all } \  x \in \mathbb{C}^n,$$
where $\mathbb{C}$ denotes the set of all complex numbers, all vectors are to be understood as column vectors, and $Ax$ denotes the usual matrix product. 
Then $T$ is of course a linear operator. 
Let $r$ and $k$ be given real numbers such that $1 \leq r < +\infty$ and $1 \leq k < +\infty$. 
Then what is the norm of $T$ 
(i) if the norm on $\mathbb{C}^n$ is given by 
$$\Vert x \Vert_k \colon= \left( \vert \xi_1\vert^k+ \cdots + \vert \xi_n \vert^k \right)^{\frac{1}{k}} \ \ \ \mbox{ for all }  \ x \colon= (\xi_1, \ldots, \xi_n) \in \mathbb{C}^n$$ 
and the norm on $\mathbb{C}^m$ is given by 
$$\Vert y \Vert_r \colon= \left( \vert \eta_1 \vert^r + \cdots + \vert \eta_m \vert^r \right)^{\frac{1}{r}} \ \ \ \mbox{ for all } \ y \colon= (\eta_1, \ldots, \eta_m) \in \mathbb{C}^m?$$
(ii) if $\mathbb{C}^n$ is given the same norm as in (i) above  but $\mathbb{C}^m$ is given the maximum norm 
$$\Vert y \Vert_{\infty} \colon= \max \left( \vert \eta_1 \vert, \ldots, \vert \eta_m \vert \right) \ \ \ \mbox{ for all } \ y \colon = (\eta_1, \ldots, \eta_m ) \in \mathbb{C}^m?$$
(iii) if $\mathbb{C}^n$ is given the maximum norm 
$$\Vert x \Vert_{\infty} \colon= \max \left( \vert \xi_1 \vert, \ldots, \vert \xi_n \vert \right) \ \ \ \mbox{ for all } \ x \colon= (\xi_1, \ldots, \xi_n ) \in \mathbb{C}^n,$$
but $\mathbb{C}^m$ is given the same norm as in (i) above?
(iv) if both $\mathbb{C}^n$ and $\mathbb{C}^m$ are given their respective  maximum norms, as in (ii) and (iii) above? 
Definition: 
Let $X$ and $Y$ be normed spaces both real or both complex, and let $T \colon X \to Y$ be a linear operator. Then $T$ is said to be bounded if there is a non-negative real number $c$ such that 
$$\Vert T(x) \Vert_{Y} \leq c \ \Vert x \Vert_{X}  \ \ \ \mbox{ for all } x \in X,$$
and then the norm $\Vert T \Vert$ of $T$ is given by  the formula 
$$\Vert T \Vert \colon= \sup \left\{ \ \frac{\Vert T(x) \Vert_Y}{\Vert x \Vert_X} \ \colon \ x \in X,  \ x \neq \theta_X \ \right\},$$
where $\theta_X$ denotes the zero vector in $X$. 
Or, equivalently, 
$$\Vert T \Vert = \sup \left\{ \ \Vert T(x) \Vert_Y \ \colon \ x \in X, \ \Vert x \Vert_X = 1 \ \right\}.$$
It can be shown that if $X$ is finite-dimensional, then $T$ is bounded. 
 A: For a matrix $A\in\Bbb R^{m\times n}$ and $1\leq p_1,p_2\leq \infty$ define
$$\|A\|_{p_1,p_2}:=\max_{x_2\neq 0}\frac{\|Ax_2\|_{p_1}}{\|x_2\|_{p_2}}.$$
Partial answer to $i)$:
Using a generalization of the Perron-Frobenius theorem you can compute some of these norms.
This is all explained in this paper (mainly Theorem 1 and 2). Actually they treat the more general case of such norms but for tensors instead of matrices. Note that this answer is also related to your problem.
I summarize here a few results:
Suppose that $A\in\Bbb R^{m\times n }$ is nonnegative (i.e. $A_{i,j}\geq 0 $ for all $i,j$) and consider the following graph associated to $A$: $G(A)=(V,E(A))$ with $V=\{1,\ldots,m\}\times \{1,\ldots,n\}$ and $(i,j)\in E(A)$ if and only if $A_{i,j}>0$. Furthermore, let us define for $1<q<\infty$ the function
$$\psi_{q}(y):= \big(|y_1|^{q-1}\operatorname{sign}(y_1),\ldots,|y_m|^{q-1}\operatorname{sign}(y_m)\big),$$
and write $q':=q/(q-1)$ the Hölder conjugate of $q$.  
Theorem:
If $A\in \Bbb R^{m\times n}$ is nonnegative, the graph $G(A)$ is connected and $1<p_1,p_2<\infty $ are such that $(p_1-1)(p_2-1)\geq 1$, the sequence $(x^k)_{k=1}^{\infty}\subset\Bbb R^n$ defined by 
$$x^0=(1,\ldots,1),\qquad x^{k+1}=\frac{\psi_{p_2'}\big(A^T\psi_{p_1}(Ax^k)\big)}{\|\psi_{p_2'}\big(A^T\psi_{p_1}(Ax^k)\big)\|_{p_2}}, \quad k=1,2,\ldots$$
satisfy 
$$ \min_{i=1,\ldots,n}\left(\frac{\Big(\psi_{p_2'}\big(A^T\psi_{p_1}(Ax^k)\big)\Big)_i}{x^k_i}\right)^{p_2-1}\leq \min_{i=1,\ldots,n}\left(\frac{\Big(\psi_{p_2'}\big(A^T\psi_{p_1}(Ax^{k+1})\big)\Big)_i}{x^{k+1}_i}\right)^{p_2-1}\leq \|A\|_{p_1,p_2}^{p_1-1}$$
and
$$ \max_{i=1,\ldots,n}\left(\frac{\Big(\psi_{p_2'}\big(A^T\psi_{p_1}(Ax^k)\big)\Big)_i}{x^k_i}\right)^{p_2-1}\geq \max_{i=1,\ldots,n}\left(\frac{\Big(\psi_{p_2'}\big(A^T\psi_{p_1}(Ax^{k+1})\big)\Big)_i}{x^{k+1}_i}\right)^{p_2-1}\geq \|A\|_{p_1,p_2}^{p_1-1}$$
for every $k\in\Bbb N$ (very useful to get upper and lower bounds quickly on the matrix norm). Moreover the sequence $(x^k)_{k=1}^{\infty}$ converges to a strictly positive global maximizer. This maximizer is the unique nonnegative critical point of the function
$$ \Bbb R^{n}\setminus{\{0\}} \to \Bbb R, \quad x_2\mapsto \frac{\|Ax_2\|_{p_1}}{\|x_2\|_{p_2}}.$$
Partial answer to $ii)$ and $iii)$: 
See @Norbert citation and this paper. I copy here the main result.
Denote by $A(:,j)$ the $j$-column of $A$ and $A(:,j)$ its $j$-th row of the matrix $A\in \Bbb R^{m\times n}$.
Theorem:
The following formulae holds:


*

*$\|A\|_{1,1}=\max\limits_{j=1,\ldots,m}\|A(:,j)\|_1$

*$\|A\|_{1,2}=\max\limits_{j=1,\ldots,m}\|A(:,j)\|_2$

*$\|A\|_{1,\infty}=\max\limits_{j=1,\ldots,m}\|A(:,j)\|_{\infty}$

*$\|A\|_{2,1}=\max\limits_{u\in\{-1,1\}^m}\|A^Tu\|_2$

*$\|A\|_{2,2}=\max\!\big\{\sqrt{\lambda}\mid \lambda \text{ is an eigenvalue of $A^TA$}\big\}$

*$\|A\|_{2,\infty}=\max\limits_{i=1,\ldots,n}\|A(i,:)\|_2$

*$\|A\|_{\infty,1}=\max\limits_{u\in\{-1,1\}^m}\|Au\|_1$

*$\|A\|_{\infty,2}=\max\limits_{u\in\{-1,1\}^m}\|Au\|_2$

*$\|A\|_{\infty,\infty}=\max\limits_{i=1,\ldots,n}\|A(i,:)\|_1$
A: It seems there is no such formula. Vaguely speaking even for simple cases this problem is NP-hard. For details see this paper
