Wikipedia:Reference desk/Archives/Mathematics/2018 September 18

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 18

Asymptotic Growth

Let A be a m-by-n matrix, and let b be a column vector with n entries.

Is $\exists c>0\forall m,n\in \mathbb {N} ,A\in M_{m,n}(\mathbb {R} ),b\in \mathbb {R} ^{m}\ :\ \max(\{0\}\cup \{i\in \{1,\dots ,n\}|\exists x\in \mathbb {R} ^{n}:Ax=b,\forall j\leq i:x_{j}\in \{0,1\}\})\leq c\cdot \log(n)$? David (talk) 10:54, 18 September 2018 (UTC)

• There must be something missing here. What do you mean exactly by O(log(n))? (If you mean you change A and b as you go through the n's, then obviously for every n you can find a A and b that require every x_i to be >1. For instance, take A the identity matrix and b the vector of all 2's.) Tigraan^{Click here to contact me} 14:01, 18 September 2018 (UTC)

You can't change A and b as you go through the n's. They're fixed. David (talk) 16:53, 18 September 2018 (UTC)

The problem is formulated in an incomprehensible way. The matrix should be actually m-by-n. Ruslik_Zero 20:27, 18 September 2018 (UTC)

For a fixed A it is very possible that you cannot get b from left multiplication by A on a vector which consists only of 0's and 1's. What if A is the identity matrix and b consists just of 2's? Am I missing something here? This is when writing out your problem in words rather than using symbols is better.--Jasper Deng (talk) 21:34, 18 September 2018 (UTC)

I fixed the typo to m-by-n.

I had in mind the convention that the maximum of an empty set is 0, so when there's no solution to the equation Ax=b the maximum is just 0. I changed my question to contain this explicitly. David (talk) 06:18, 19 September 2018 (UTC)

• First of all, please WP:STRIKE instead of making "sneak" edits. Second, I assume b is now a column of m, not n, entries, otherwise the dimensions do not match in Ax=b. Third, there still is a quantifier problem around the definition of n - O(log(n)) implies we go through the n, but let A be a m-by-n matrix... implies it is fixed at the start; if you do not see why, try using quantifiers instead of the big-O notation. Tigraan^{Click here to contact me} 09:03, 19 September 2018 (UTC)

I re-edited my question. David (talk) 10:07, 19 September 2018 (UTC)

With the current wording, the proposition is at least understandable, but obviously false. For every n it is easy to pick a pair A,b such that there is a solution with all x_j in {0,1}, thus making the max(...) equal to n. For instance, make all elements of A and b zeros, and any x will do (including those whose only elements are zeros and ones). Tigraan^{Click here to contact me} 11:24, 19 September 2018 (UTC)