The Problem: Let $A \in O(n)$, the set of $n \times n$ matrices which satisfy $A^t = A^{-1}$. Denote the entries of $A$ by $a_{i,j}$. I wish to show the following bounds:
$$n \le \sum_{i=1}^n \sum_{j=1}^n \left| a_{i,j} \right| \le n \sqrt{n!}$$
Context: This comes up as part of a homework assignment, so I would prefer only nudges in the right direction. I have proved a couple of similar identities for orthogonal matrices $A$:
$$\sum_{i=1}^n \sum_{j=1}^n a_{i,j}^2 = n \qquad \left| \sum_{i=1}^n \sum_{j=1}^n a_{i,j} \right| \le n$$
The first was fairly easy since the sum in question is essentially $\langle A,A \rangle_F$ where $\langle \cdot, \cdot \rangle_F$ denotes the Frobenius inner product, which can also be given by $\langle B,C \rangle_F = \operatorname{trace}(B^t C)$ for real matrices. Using that $A^t = A^{-1}$ made that easy.
The second followed in part from the first, alongside using Cauchy-Schwarz. You can rewrite the sum in terms of the sum of the column vectors instead and apply Cauchy-Schwarz on the dot product with the all-ones vector. You get two sums in the end, one of which is precisely that in part (a).
Granted those are mostly the high points. However, I'm not really sure how to prove either of the desired bounds for the problem I stated at the outset. The triangle inequality by itself isn't enough to get the lower bound of $n$, and I can't quite figure out a framing of the problem or an inner product to use to make use of Cauchy-Schwarz for either bound. I've also struggled to find any other case of someone asking this or proving this elsewhere online, MSE included.
Does anyone have any ideas to lead me in the right direction?
Update: Proving the upper bound is actually quite easy, thanks to a nudge from copper.hat. Define $\mathcal O$ to be the matrix consisting of all ones, and define $\widetilde A$ to be the matrix such that $\widetilde a_{i,j} = |a_{i,j}|$. Then we see that
$$\sum_{i=1}^n \sum_{j=1}^n \left| a_{i,j} \right| = \langle \widetilde A, \mathcal O \rangle_F$$
From here, we just square both sides, apply Cauchy-Schwarz and one of the already-proven identities, and with a little algebra easily show
$$\sum_{i=1}^n \sum_{j=1}^n \left| a_{i,j} \right| \le n \sqrt n$$
This is actually a tighter bound than $n \sqrt{n!}$ (as $n \le n!$ for all $n \in \Bbb Z^+$, trivially). So this somewhat makes me wonder what method was originally intended.
Still not sure on the lower bound though... But thanks for your insight copper.hat!
$ \newcommand{\ipf}[2]{ \Big \langle #1, #2 \Big \rangle_F} \newcommand{\ds}{ \sum_{i=1}^n \sum_{j=1}^n} \newcommand{\AA}{\widetilde{A}} \newcommand{\aa}{\widetilde{a}} \newcommand{\OO}{\mathcal{O}} $ Posting an answer to this since copper.hat and Gerry Myerson were gracious enough to fill me in on enough details to move forward.
The Upper Bound:
Define $\AA$ to be the matrix that is only absolute values of $A$'s entries, i.e. $\aa_{i,j} = |a_{i,j}|$. Denote by $\OO$ the all-ones matrix. Obviously, we can then see that
$$\ds |a_{i,j}| = \ds |a_{i,j}| \cdot 1 = \ipf \AA \OO$$
We can then square both sides and apply Cauchy-Schwarz:
$$\left( \ds |a_{i,j}| \right)^2 = \ipf \AA \OO^2 \le \ipf \AA \AA \ipf \OO \OO$$
The former is clearly given by
$$\ipf \AA \AA = \ds |a_{i,j}||a_{i,j}| = \ds |a_{i,j}|^2 = \ds a_{i,j}^2 = n$$
from one of the equalities I already proved. Meanwhile,
$$\ipf \OO \OO = \ds 1 = n^2$$
more trivially. Therefore, we've seen that
$$\left( \ds |a_{i,j}| \right)^2 \le n \cdot n^2 = n^3 \implies \ds |a_{i,j}| \le n^{3/2} = n \sqrt n$$
This is a tighter bound than originally desired, but works since $n \le n!$ $\forall n \in \Bbb Z^+$ trivially.
The Lower Bound:
Recall: the columns and rows of orthogonal matrices form orthonormal bases of $\Bbb R^n$. In particular, that will mean that the $j$th column (or row, but I prefer thinking in columns) of $A \in O(n)$, for any $j$ we like, will have unit length under the Euclidean norm, i.e.
$$\sqrt{ \sum_{i=1}^n a_{i,j}^2 } = 1 \implies \sum_{i=1}^n a_{i,j}^2 = 1$$
Note that we're summing entirely nonnegative quantities. Therefore, between the above and the fact that this applies for all $j$, we have
$$a_{i,j}^2 \in [0,1] \implies a_{i,j} \in [-1,1]$$
for all $i,j \in \{1,2,\cdots,n\}$. We also note that $x^2 \le x$ on $[0,1]$ and $x^2 \le -x$ on $[-1,1]$; or, more compactly, $x^2 \le |x|$ on $[-1,1]$. Therefore, now that we know $a_{i,j} \in [-1,1]$ $\forall i, j$, then
$$a_{i,j}^2 \le |a_{i,j}|$$
If we sum over both sides over the full range of $i,j$, then the inequality is maintained (as we're adding only nonnegative terms, all of which fulfill that relation) and we have
$$\ds a_{i,j}^2 \le \ds |a_{i,j}|$$
Note, however: the right-hand sum is precisely the one we want a bound on. Meanwhile, the left-hand one is one for which I already know an exact value: as stated in the question body itself, it is $n$. Thus,
$$n\le \ds |a_{i,j}|$$
giving the desired lower bound.