# Under What Conditions $||UP||_1 \geq ||P||_1$ for All Unitary $U$?

Consider a sparse $$N \times N$$ matrix $$P$$ with at most $$2N$$ nonzero entries and $$\text{diag}(P) = 1$$. Define the norm $$|P|_1$$ as the sum of the absolute values of all entries in $$P$$, i.e., $$|P|_1=\sum_{i, j}\left|P_{i j}\right|$$.

For which matrices $$P$$ does the inequality $$|UP|_1 \geq |P|_1$$ hold for every unitary matrix $$U$$, while ensuring that $$\text{diag}(UP) = 1$$?

Here, $$|UP|_1$$ is calculated as $$\sum_{i, j}\left|(UP)_{i j}\right|$$, where $$(UP)_{i j}$$ is the $$(i, j)$$ entry of the matrix product $$UP$$, and can also be expressed as $$\sum_{i, j}\left|u_i^T p^j\right|$$. (For a matrix $$X$$, let $$x_i$$ and $$x^j$$ denote the $$i$$-th row and $$j$$-th column of $$X$$, respectively.)

## Background:

In my research, I developed an algorithm to estimate $$P$$, and it generally converges correctly (I'm sorry details and code cannot be shared). And if my algorithm can find the correct solution, this problem is a corollary. The algorithm's effectiveness suggests that there might be a broad class of matrices $$P$$ for which this condition holds.

Empirically, when $$P$$ is initialized with $$N$$ off-diagnal elements randomly chosen within the range from -1 to 1 , convergence is fast. However, when the elements are all set to 1 , convergence typically fails. I'm looking to understand what specific properties or characteristics of $$P$$ ensure the condition $$\|U P\|_1 \geq\|P|_1$$ is always met.

## Update:

Considering a simplified scenario where all entries of $$P$$ are positive might provide a useful starting point. When analyzing $$\|UP\|_1 \geq \|UP_1\|_1 = \|Up\|_1$$, with $$P_1$$ defined as a column vector of all ones, we examine $$\|Up\|_1$$ by evaluating the sum of the magnitudes of the projections of $$U$$'s row vectors onto $$p$$. Here, $$p = P_{1,1}$$ can be any column vector, and we express:

$$\|Up\|_1 = \sum_i |u_i p| = \sum_i \|u_i\|_2 \|p\|_2 \cos \theta_i,$$

where $$\cos \theta_i$$ is the angle between $$p$$ and $$u_i$$. This formulation simplifies to the minimum at $$\|p\|_2$$, but unfortunately, $$\|p\|_2$$ is not necessarily greater than $$\|P\|_1$$. This observation suggests that the initial diagonal and sparsity constraints might need to be revisited or revised in the theoretical model.

### Update 8.2

To confirm the correctness of the problem, I have developed a program. Dealing with the constraint of unitarity was challenging. My approach involved projecting a non-unitary matrix onto the space of unitary matrices, which is an application of the Orthogonal Procrustes problem.

The code is iterative, ensuring that matrix $$U$$ ultimately remains unitary while also maintaining that $$\operatorname{diag}(UP) = 1$$.

For those interested in reviewing or utilizing the methodology, the code can be accessed through the following link: Code.

I welcome any feedback or suggestions on the implementation and the theoretical approach.

• Some new update. diag(UP)=1 might be redundant Commented Aug 1 at 23:32
• Are there results in literature for $\min_{U \in U(n)}|UP|_1$? Have you tried solving for the critical points of the function $f(U) = |UP|_{1}$ on the manifold $U(n)$? You can get some equations for setting derivative to $0$ that may help. At worst, you can do numerical optimization. Commented Aug 2 at 1:12
• @Mason I haven't explored $\min _{U \in U(n)}|U P|_1$. Actually, I don't know how to solve for the critical points you mentioned. Can you provide more details? Yes, that's what I'm currently working on. I am mainly doing numerical optimization, and my program converges to the correct results in almost all cases, so I guess there must be some broader mathematical conclusion. Commented Aug 2 at 1:28
• Let $U$ be a minimizer. The critical point equation is $df(U) = 0$, which here means $\sum_{j, k = 1}^{N}\text{sgn}(|(UP)_{j,k}|)|(AP)_{j, k}| \ni 0$ for all $A$ with $A^T = -A$. Oh this is assuming you are working with real matrices only. For complex matrices it will be different. Commented Aug 2 at 1:51
• @Mason Thanks for your help. Yes. I'm only working with real matrices. Do you mean this $\sum_{j, k=1}^N \operatorname{sgn}\left((U P)_{j, k}\right)\left|(A P)_{j, k}\right| \ni 0$? what does $\ni$ here mean? Do you mean there exist A to let LHS=0 Commented Aug 2 at 2:09