Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
No. Enumerate all positive integers which are not powers of 2$2$: $3=n_1<n_2<n_3<\dots$ and partition positive integers onto pairsinto two-element sets $(n_i,2^{i-1})$$\{n_k,2^{k-1}\}$. TakeLet $a_{i,j}=1$ wheneverif the set $(i,j)$$\{i,j\}$ is our pairsuch a two-element set, and let $a_{i,j}=0$ otherwise. We get a symmetric bistochastic matrix, and all ones's$1$'s are only in the rows or columns indexed by a power of 2$2$. We have $O(\log n)$ such entries in a square $\{1,2,\dots,n\}^2$.
No. Enumerate all positive integers which are not powers of 2: $3=n_1<n_2<n_3<\dots$ and partition positive integers onto pairs $(n_i,2^{i-1})$. Take $a_{i,j}=1$ whenever $(i,j)$ is our pair. We get a symmetric bistochastic matrix, and all ones's are only in the rows or columns indexed by a power of 2. We have $O(\log n)$ such entries in a square $\{1,2,\dots,n\}^2$.
No. Enumerate all positive integers which are not powers of $2$: $3=n_1<n_2<n_3<\dots$ and partition positive integers into two-element sets $\{n_k,2^{k-1}\}$. Let $a_{i,j}=1$ if the set $\{i,j\}$ is such a two-element set, and let $a_{i,j}=0$ otherwise. We get a symmetric bistochastic matrix, and $1$'s are only in the rows or columns indexed by a power of $2$. We have $O(\log n)$ such entries in a square $\{1,2,\dots,n\}^2$.
No. Enumerate all positive integers which are not powers of 2: $3=n_1<n_2<n_3<\dots$ and partition positive integers onto pairs $(n_i,2^{i-1})$. Take $a_{i,j}=1$ whenever $(i,j)$ is our pair. We get a symmetric bistochastic matrix, and all ones's are only in the rows or columns indexed by a power of 2. We have $O(\log n)$ such entries in a square $\{1,2,\dots,n\}^2$.
