Computaional Complexity of Frobenius Norm

How can I calculate the computaional complexity of Frobenius norm of each column vector(M X 1) in a M X N matrix and finally sorting the norm values in descending order? To clarify I have N-column vectors in a matrix and I want to calculate the magnitude of each column and finally arranging in a descending order in an algorithm. So what will be the computational complexity of doing this task in a a Big-O notation?

DQQD algorithm for Frobenius numbers

As a hobbyist problem-solver, recently I stumbled upon two problems related to Frobenius numbers on one of competitive coding websites I like: Zombie Apocalypse: the Last Number Standing and Matunga coins. I did some research (i.e. googling), found some information, and most notably a paper which describes a couple of approaches: Faster Algorithms for Frobenius Numbers. I succesfully managed to implement Round Robin, BFD and BFDU algorithms and with that I managed to solve the tasks (yay!). However I also wanted to implement QDDQ(U) algorithms described there, and I cannot get the implementation right.

Pseudocode for BFD presented on page 9 is rather clear and I managed to implement it without any special problem. Adding one small update step I also got BFDU right. But with pseudocode for DQQD on p. 15, I cannot get past the first iteration of the example.

Pseudocode as given in the paper:


enter image description here


  • Either I am getting things mixed up because of inconsistent indexing used in the paper (1-based for vector A, 0-based for other stuff), or

  • I am misinterpreting some ambiguous symbols (for example, w mutates through the iteration, and Qw can mean different things, depending on whether we use Qw determined on the beginning of the iteration, or we use different Qw every time w changes), or

  • there is a typo or some other mistake somewhere in the pseudocode, or

  • everything is OK there and it’s just my mathematical ineptitude getting in the way. Unfortunately, I am not a mathematician, and theoretical basis for the algorithm is beyond my comprehension skills 🙁 Maybe I should just GIT GUD?

I already tried changing here-or-there, but it was just a guessing game. I tried to find other implementations of DQQD, especially one in Mathematica, but they do not seem to be available. I also do not need to have the code written for me. All I need is someone to take a peek at pseudocode of DQQD in mentioned paper, and, if possible, try to implement it or verify it in any way if it’s correct and I suck, or if it indeed has some typos, mistakes, or other issues.

Next step: overkilling the problem with FROBENIUS NUMBERS BY LATTICE POINT ENUMERATION 🙂

Lower and upper bounds of the distance between two Frobenius numbers

I consider two sequences of numbers: $ A=\{a_1,…,a_{m-1},n\}$ and $ B=\{n-a_{m-1},…,n-a_1,n\}$ , where $ a_1 < a_2 < … < a_{m-1} < n$ and $ \gcd(A) = \gcd(B) = 1$ .


I investigate the lower and upper bounds of the distance between two Frobenius Numbers:

$ Dist Lower Bound \le \left| F(A) – F(B) \right| \le Dist Upper Bound $

I found only one trivial estimate for lower bound: It is known that $ F(a_1,…,a_m) \ge a_1 – 1$ if $ a_1 \ge 2$ . Using this property, we obtain that:

$ \left| F(A) – F(B) \right| \ge \left| n-a_{m-1}-a_1 \right|$ .


Also, I investigate the lower and upper bounds of the sum of two Frobenius Numbers:

$ Sum Lower Bound \le F(A) + F(B) \le Sum Upper Bound $

I found only one trivial estimate for upper bound: I am using simple way. I took well-known estimates and combine it because I having knowledge about $ a_{m-1}$ .

$ 1. F(a_1,…,a_m) \le 2a_{m-1} \lfloor{\frac{a_m}{m}}\rfloor – a_m = 2a_{m-1} \lfloor{\frac{n}{m}}\rfloor – n$ .

$ 2. F(b_1,…,b_m) \le 2b_m \lfloor{\frac{b_1}{m}}\rfloor – b_1 = 2n \lfloor{\frac{n-a_{m-1}}{m}}\rfloor – n + a_{m-1}$ .


I am convinced that there are other nearer solutions. I will be grateful for any help in search $ Sum Lower Bound $ and $ Dist Upper Bound $ as well as improving my estimates.

About Frobenius Number can be read here: link 1, link 2.

The Frobenius at the infinite prime?

For simplicity, suppose $ X$ is a smooth $ n$ -dimensional variety defined over $ \mathbb{Q}$ . Then the etale cohomology of $ X$ , denoted by $ H^i_{\text{et}}(X,\mathbb{Q}_\ell)$ , gives a representation of the Galois group $ \text{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$ , which is only ramified at finitely many prime numbers. Suppose $ p\neq \ell$ is an unramified prime, then there is a well-defined (geometric) Frobenius action on $ H^i_{\text{et}}(X,\mathbb{Q}_\ell)$ . \begin{equation} \text{Fr}_p:H^i_{\text{et}}(X,\mathbb{Q}_\ell) \rightarrow H^i_{\text{et}}(X,\mathbb{Q}_\ell). \end{equation} Is there a reasonable way to define the limit $ $ \lim_{p \rightarrow \infty}\text{Fr}_p,$ $ which acts on a cohomology space?

The thing that comes to my mind is that the completion of $ \mathbb{Q}$ at the infinite prime is $ \mathbb{R}$ , while the Galois group $ \text{Gal}(\mathbb{C}/\mathbb{R})$ is generated by the conjugation $ c$ , and it has an action \begin{equation} c:H^i(X(\mathbb{C}),\mathbb{R}) \rightarrow H^i(X(\mathbb{C}),\mathbb{R}). \end{equation} I don’t know whether it is reasonable to say $ $ \lim_{p \rightarrow \infty}\text{Fr}_p=c?$ $ One thing that confuses me is that the Frobenius contains lots of arithmetic information of $ X$ , while $ c$ does not. Another thing that confuse me is that, when define the full $ L$ -function of $ X$ , at the (unramified) prime number $ p$ , the local $ L$ -factor is defined by the characteristic polynomial of the Frobenius $ \text{Fr}_p$ . While at the infinite prime of $ \mathbb{Q}$ , the local $ L$ -factor is given by the Gamma function, which (to me) does not look like the “characteristic polynomial” of the complex conjugation. (Even though complex conjugation plays an important part in the definition of the $ L$ -factor at infinite prime.)

$p$-adic realisation of Kummer motive and Frobenius matrix

Suppose $ M$ is an object in the abelian category of mixed Tate motives over $ \mathbb{Q}$ , and it is an extension of $ \mathbb{Q}(0)$ by $ \mathbb{Q}(1)$ \begin{equation} 0 \rightarrow \mathbb{Q}(1) \rightarrow M \rightarrow \mathbb{Q}(0) \rightarrow 0. \end{equation} Suppose the Hodge realisation of $ M$ is the one associated to $ \log u, u \in \mathbb{Q}^*$ , i.e. $ u$ is a nonzero rational number. Suppose $ p$ is an unramified prime of $ M$ , and in the $ p$ -adic realisation of $ M$ , what is the matrix associated to the geometric Frobenius?

The matrix must be of the form \begin{pmatrix} 1, ~~~0 \ *, 1/p \end{pmatrix} but is the unknown $ *$ in the matrix just the $ p$ -adic value of $ \log u$ , i.e. the $ p$ -adic logarithm valued at $ u$ .

Remark, I do not understand the $ p$ -adic realisations of the mixed Tate motives very well, so the statement of this question might not be very rigorous. References about the $ p$ -adic realisations of mixed Tate motives are welcomed.

Relation between Frobenius norm, infinity norm and sum of maximums

Let $ A$ be a $ n \times n$ matrix so that the Frobenius norm squared $ \|A\|_F^2$ is $ \Theta(n)$ , the infinity norm squared $ \|A\|_{\infty}^2=1$ . Is it true that $ \sum_{i=1}^n\max_{1\leq j\leq n} |A_{ij}|^2$ is $ \Omega(n)$ ? Assume that $ n$ is sufficiently large.

I cannot find a relation between matrix norms that can show this. For the spectral norm it is not true as there is a nice costrunction.

Thanks!

Relation between Frobenius, spectral norm and sum of maximums

Let $ A$ be a $ n \times n$ matrix so that the Frobenius norm squared $ \|A\|_F^2$ is $ \Theta(n)$ , the spectral norm squared $ \|A\|_2^2=1$ . Is it true that $ \sum_{i=1}^n\max_{1\leq j\leq n} |A_{ij}|^2$ is $ \Omega(n)$ ? Assume that $ n$ is sufficiently large.

I cannot find a relation between matrix norms that can show this. The idea behind this question is that there are many singular values of $ A$ that are $ \Theta(1)$ .

Thanks!

Gradient of squared Frobenius norm w.r.t. a vector

I’d like to find the gradient of $ \frac{1}{2}\| xx^T – A \|^2_F$ with respect to $ x$ , where $ x \in \mathbb{R}^n$ , $ A \in \mathbb{R}^{n \times n}$ .

I’m not sure my result is correct. Hope somebody will help me find a mistake.

I got something like that:

\begin{aligned} d(\frac{1}{2} \|xx^T – A\|^2_F) \rangle &= \frac{1}{2} d(\mathrm{tr}((xx^T – A)(xx^T – A)^T) \ &= \frac{1}{2} d(\mathrm{tr} (xx^Txx^T) – \mathrm{tr}(x^T(A + A^T)x) + \mathrm{tr}(AA^T)) \ &= \frac{1}{2}d(\|x\|^4_2 – \mathrm{tr}(x^T(A + A^T)x) + \|A\|^2_F) \ &= \frac{1}{2}(d(\|x\|^4_2) – d(\mathrm{tr}(x^T(A + A^T)x)) + d(\|A\|^2_F) ) \ &= (2x^Txx^T – x^T(A + A^T))dx \end{aligned}

And if $ f: \mathbb{R}^n \rightarrow \mathbb{R}$ , we have $ df(x) = (\nabla f(x))^Tdx$

So I got the result: $ \nabla f(x) = 2xx^Tx – (A + A^T)x$

As I said before I’m not sure it’s right. I checked the result using scipy.optimize.check_grad(), but it returned a value much greater than zero. It seems that I made a mistake somewhere. What am I doing wrong?