# Total Variation Distance between Two Matrices

I have two $$n \times n$$ matrices $$P$$ and $$Q$$. They are given as follows:

$$P = \begin{bmatrix}p_{11}&p_{12}&........&p_{1n}\\p_{21}&p_{22}&........&p_{2n}\\...&...&........&...\\...&...&........&...\\p_{n1}&p_{n2}&........&p_{nn}\end{bmatrix}$$

$$Q = \begin{bmatrix}q_{11}&q_{12}&........&q_{1n}\\q_{21}&q_{22}&........&q_{2n}\\...&...&........&...\\...&...&........&...\\q_{n1}&q_{n2}&........&q_{nn}\end{bmatrix}$$

Now, I know that the Total Variation Distance between $$P$$ and $$Q$$ is at most $$\delta$$, i.e., $$d_{TV}(P,Q) \leq \delta$$. Is there any way I can relate this $$\delta$$ to the difference between each entry, for example $$(p_{11} - q_{11})$$, or $$(p_{12} - q_{12})$$, and so on?

• Can you define the total variation distance that you are using here? (The one I have in mind is $d_{\rm TV}(P, Q) = \frac{1}{2} \sum_{i,j} |P_{ij} - Q_{ij}|$, but perhaps yours is different.) Jul 7, 2020 at 4:10
• $d_{TV}(P,Q) = \frac{1}{2}||P-Q||_1$. It's the same as your definition Jul 7, 2020 at 4:11

No. In general, the best you can say is that $$|p_{ij} - q_{ij}| \leq 2\delta$$ for all $$i,j$$. This is clearly tight: take $$P = 2\delta e_i e_j^T$$ and $$Q = 0$$.
(Note: this is a consequence of the general fact that a $$\ell_1$$ norm implies a very pessimistic bound on the $$\ell_\infty$$ norm.)
• No real reference. You have for a general vector $x \in \mathbb{R}^n$: $\|x\|_\infty \leq \|x\|_1 \leq n \|x\|_\infty$, by definition. Jul 7, 2020 at 4:21