0
votes
1answer
18 views

Construct matrix of ones and zeros based on sequences

We are given ($a_1,a_2,....,a_m$) and ($b_1, b_2,....,b_n$) sequences with non-negative integers. Decide whether it's possible and if it is construct a matrix $\Re^{m x n}$ of ones("1") and ...
2
votes
1answer
31 views

Proving that if $n\times n$ Hadamard matrix exists, then 4 divides $n$

Im looking for an explanation of the following: a standard way to prove that, if there exists Hadamard matrix of dimension $n > 2$, then $4|n$, is to suppose that without loss of generality every ...
2
votes
1answer
40 views

How do you handle this kind of probability?

What is the probability of selecting a singular matrix from $\Bbb{R}^{3\times 3}$? I calculated it to be zero based on their being approximately $9$ degrees of freedom to choose entries of $A$ such ...
1
vote
1answer
59 views

counting Number of matrices

We have a $2 \times 2$ matrix. We are given the trace of the matrix as $N$. Also, all elements of the matrix are greater than or equal to $1$. And, the determinant of matrix is $\geq 1$. QUESTIONS: ...
2
votes
2answers
71 views

Powers of permutation matrices.

Let $P$ be a permutation matrix obtained by the identity matrix by switching 2 rows $n$ times, (with no two rows switched more than one time). How to show that $$P^{\ n+1} = I$$? Is it true that, ...
0
votes
2answers
46 views

How many skew symmetric matrices are possible?

I just heard the term skew symmetric matrix and upon discovering what it was, I thought to myself, "Jeez, there could only be so many of those." I'm not good with the whole permutation thing and this ...
1
vote
1answer
45 views

On Adjacency Matrix of a Graph with a Cut Vertex and a Bridge

Let $G$ be a graph. If $v_i$ (resp. $v_iv_j$) is a cut vertex (resp. a bridge) of $G$, what can you say about its adjacency matrix $A(G)$?
1
vote
1answer
146 views

Number of binary n x m matrices, with at most k consecutive number of 1 in each column

I am trying to compute the number of $n x m$ binary matrices with at most $k$ consecutive values of $1$ in each column. I've figured out that I it will be enough to find the vectors with $1$ column ...
1
vote
0answers
50 views

Prove that the minimum of row sums of a nonnegative symmetric matrix is preserved

Let $A$ be an $n\times n$ adjacency (nonnegative, irreducible and symmetric) matrix with zeros on the diagonal. Denote $i$-th row sum of $A^k$ as $r^{(k)}_i$, where $k\geq1$. I want to prove that if ...
1
vote
1answer
22 views

Information content of an unlabelled matrix

I'm trying to get an idea of the amount of information that is "stored" in an "unlabelled" matrix. I assume that the vector $(x,y,z)$ contains more information than the set $\{x,y,z\}$. But purposely ...
7
votes
1answer
241 views

Number of binary $M\times N$ matrices with even row sums, even col sums and $K$ ones, $K$ even

A combinatorial problem arising with certain checksums: When sending messages, the user data are protected by adding a parity bit for bit positions $1\dots8$ and a parity bit for each byte. So, the ...
1
vote
4answers
116 views

How to tell if two matrices are equal up to a permutation

Given two real rectangular matrices A, B how can I tell if they are equal up to a permutation of their rows/column without trying all possible permutations? (This is closely related to the question I ...
0
votes
0answers
36 views

Summing the product of combinations of matrix elements

I have a situation where I have an $NxN$ matrix $A$ where each element $a_{i,j}\in\mathbb{R}_{\leq 0}$. I would like to consider the set of all collections of elements such that each collection of $N$ ...
6
votes
3answers
278 views

Number of matrices with no repeated columns or rows

If you consider all $10$ by $15$ matrices with entries that are either $0$ or $1$, there are ${2^{15} \choose 10}$ with no repeated rows (up to row permutation) and ${2^{10} \choose 15}$ with no ...
1
vote
2answers
38 views

combinatorics - permutations question, possibly with pigeon hole

Let $A \in Mat_n(\mathbb R)$ such that $\forall i,j: a_{ij}\geq 0$ We are given: $$\forall j: \sum_{i=1}^n a_{ij}=\sum_{i=1}^n a_{ji}=1$$ show there's a permutation $\pi \in S_n$ such that $$\forall ...
0
votes
0answers
30 views

Can one find arbitrarily large subsets of a vector space of dimension n, such that any subset of n vectors is a basis?

I thought of this mildly interesting question earlier this evening: Given a vector space $V$ of dimension $n$, for what values of $m > n$ is it possible to create a set $S$ of $m$ vectors such ...
0
votes
1answer
53 views

number of ways to fill a 2D grid

We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
3
votes
3answers
101 views

Find three $10\times10$ orthogonal Latin squares.

Does anyone know if there is a mathematical "trick" in finding mutually orthogonal Latin squares? Or is it basically trial and error?
0
votes
1answer
45 views

Inverse of particular matrix

I have a $ n \times n $ matrix with the following form: $$ \begin{pmatrix} a^n+b^n & C_{n,1} \; a b^{n-1} & \cdots & C_{n,n-1} \; a^{n-1} b \\ C_{n,n-1} \; a^{n-1} b & a^n + b^n & ...
1
vote
3answers
88 views

Generalization of permutation matrix

For integers $n$ and $k$, I am interested in $n\times n$ matrices with exactly $k$ non-zero entries in each row and each column. The case $k=1$ corresponds to (generalized) permutation matrices. In ...
3
votes
4answers
166 views

Coefficient of $x^n$ in the series

How will we find the coefficient of $x^n$ in the following series: $$(1+x+2x^2+3x^3+...)^n$$ Please suggest if there is some formula or if it can be computed using the computer in $\log n$ time. I ...
5
votes
1answer
69 views

Question about matrices whose row and column sums are zero

I am interested in $n \times n$ matrices over some field $K$ all whose rows and all whose columns sum to zero. First question: do these matrices have a name? Pending an answer I will call these ...
8
votes
0answers
99 views

How many arrays with crossed cells, order of rows/columns irrelevant

I've been struggling with this simple problem for months though as I am a newbie to… well, maths, there's high chance someone more educated than myself may get it right! Let's consider an array or a ...
6
votes
0answers
48 views

How many pairs of nilpotent, commuting matrices are there in $M_n(\mathbb{F}_q)$?

As a follow-up to this question, I've been doing some work counting pairs of commuting, nilpotent, $n\times n$ matrices over $\mathbb{F}_q$. So far, I believe that for $n=2$, there are $q^3+q^2-q$ ...
8
votes
1answer
88 views

How many matrices in $M_n(\mathbb{F}_q)$ are nilpotent?

I have strong computational evidence to think that the answer is $q^{n(n-1)}$, although a proof eludes me. Any ideas?
0
votes
3answers
159 views

What is the *correct* (matrix) square-root of $A_2=\begin{bmatrix} 0&-1 \\ 1& 2 \end{bmatrix} $?

In studying the problem of some trivial(?) generalization of the NSW-numbers [ OEIS,wikipedia ] (see my other related question) there came up one detail where I think I have the correct answer but ...
1
vote
1answer
121 views

Uniqueness of doubly stochastic matrix descomposition

this is my first question in the site. Thanks in advance for all answers. It is well known that each bistochastic matrix can be represented as a convex combination of permutation matrices. I am ...
4
votes
1answer
84 views

Periodic (-1,0,1) matrices of two types

similar question: http://mathoverflow.net/questions/9547/how-to-construct-matrices-with-periodicity Definition: a (-1,0,1) matrix is a matrix with entries either -1, 0 or 1. I am trying to understand ...
2
votes
1answer
61 views

Using matrix theory to solve this problem

I'm sorry that I couldn't find a better title for this. I was wondering if my solution is valid for the following problem, or if I've made some mistake. Problem: Let $N=\{a_1, \dots, a_n\}$ be a ...
3
votes
2answers
151 views

Characterizing sums of permutation matrices

Given an $n$ by $n$ matrix $A$ whose rows and columns sum to $m \in \mathbb N$ and entries are nonnegative integers, does there exist a permutation matrix $P$ such that $A - P$ has only nonnegative ...
2
votes
1answer
78 views

How many Jordan normal forms are there when the characteristic polynomial is $(\lambda+4)^5(\lambda-2)^2$?

Let $A\in M_7(\mathbb{C})$ be a matrix in with the characteristic polynomial $p(A)=(\lambda+4)^5(\lambda-2)^2$. I need to find all Jordan normal forms for this. I think that i can use that the ...
1
vote
2answers
99 views

Problem regarding filling squares inside a $n\times n$ grid.

Assuming a $n\times n$ square grid, what is the most number of squares that can be filled in such that there are no completed rows, columns, or diagonals? Is there a formula to calculate this? ...
0
votes
0answers
32 views

Number of square ($0$, $1$)-matrices with $1$s confined to main diagonal & contiguous sub & superdiagonals with column and row sums in {$0$, $1$}

What is the number of n x n $(0,1)$-matrices having exactly k $1$s ($0$ $\leq$ k $\leq$ n), with the $1$s confined to the main diagonal, plus the first md subdiagonals, plus the first mu ...
0
votes
2answers
144 views

Possibility of making diagonal elements of a square matrix 1,if matrix has only 0 or 1

Let $M$ be an $n \times n$ matrix with each entry equal to either $0$ or $1$. Let $m_{i,j}$ denote the entry in row $i$ and column $j$. A diagonal entry is one of the form $m_{i,i}$ for some $i$. ...
0
votes
1answer
40 views

Can this famous theorem extended to the weighted undirected graphs?

There is well-known bound on the largest eigenvalue of graphs that says $$\sqrt{d_{max}}\leq \lambda_{max}$$. Is it also true for weighted graphs? (Where as usual, the degree of a vertex in a weighted ...
3
votes
3answers
102 views

Combinatorics inside of $GL(n,q)$

I'm studying conjugacy classes of subgroups of $GL(n,q)$ of the form $(\mathbb{Z}/p\mathbb{Z})^r$ where $q=p^d$ and $r$ is some non-negative integer. I've been able to show that for $n=p=2$ and for ...
2
votes
0answers
79 views

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
1
vote
1answer
48 views

Normalizing a matrix with row and column swapping

How do you canonicalize a matrix over column- and row-swap operations? Or more specifically, does there exist a function f(M) such that ...
2
votes
1answer
87 views

Show the following matrix recursion is symmetric

I need to show the following matrix equation is symmetric and I'm not sure where to start: $A_i=\sum_{j_1=1}^{i-2}2(i-j_1-1){i-2 \choose j_1-1}A_{j_1}\Big(\sum_{j_2=1}^{i-j_1-1}{i-j_1-2 \choose ...
1
vote
2answers
40 views

Counting the number of matrices

Kindly help me solve this question. Let $$S=\left\{A=[a_{ij}]_{5\times 5}\;\middle\vert\;\begin{array}{c} a_{ij}=0\text{ or }1\forall i,j,\\ \textstyle\sum_j a_{ij}=1\forall i,\\ \text{ and ...
1
vote
1answer
88 views

Proof of Nonnegativity Inequality

Prove the Inequality: $$\sum_{i,j}\left ( (PAQ)_{i,j}\frac{B_{i,j}^2}{A_{i,j}}- (PBQ)_{i,j}B_{i,j}\right ) \geqslant 0$$ Given that: $P$ and $Q$ are $n$x$n$ and $m$x$m$ symmetric matrices, $A$ ...
-1
votes
1answer
39 views

What elements does this set have

What elements does the set $T_{2,3}$ in this paper exactly have? and how about $T_{3,3}$, and $T_{3,4}$?
7
votes
1answer
98 views

Matrix + combinatorial or conditional probability: bit patterns

I'm trying to get my head around a problem, and it's not working. The problem: consider an NxN matrix that represents a binary number. For instance, a 4x4 matrix is a 16 bit number, a 6x6 matrix is ...
3
votes
1answer
230 views

Number of $(0,1)$ $m\times n$ matrices with no empty rows or columns

I am looking to calculate the number of $m\times n$ matrices which have no empty rows or columns (at least one $1$ in each row and column). I have looked at the answers to a few similar questions ...
8
votes
1answer
126 views

Counting subsets of lattice points

Let $n\ge 2$, and consider the set of $\binom{n}{2}$ lattice points in the interior of the triangle with vertices $(0,0)$, $(0,n+1)$ and $(n+1,n+1)$. For $r\le \binom{n}{2}$, let $f(n,r)$ be the ...
3
votes
1answer
112 views

A variation of Cauchy's determinant

Prove the following identity: $$\det_{_{1\leq i,j \leq n}}\left(\frac{1}{(x_i+y_j)^2}\right)=\det_{_{1\leq i,j \leq n}}\left(\frac{1}{x_i+y_j}\right)\text{perm}_{_{1\leq i,j \leq ...
1
vote
0answers
131 views

How to find the parity check matrix for 101101101101101 in Hamming Codes (15,11) in graphic way?

I am trying to find hamming matrix for safe coded word: 101101101101101 My questions are: 1) What matrix check I should use? I mean there are two types of 15,11 => one starting with 1111 and one ...
1
vote
2answers
123 views

Computing positive semidefinite (PSD) rank with mathematical software

I would like find positive semidefinite (PSD) rank or a decomposition for 10~15 size square nonnegative matrices with the aid of some mathematical software. I wonder if it is feasible with standard ...
5
votes
1answer
71 views

Is there a name for this given type of matrix?

Given a finite set of symbols, say $\Omega=\{1,\ldots,n\}$, is there a name for an $n\times m$ matrix $A$ such that every column of $A$ contains each elements of $\Omega$? (The motivation for this ...
8
votes
4answers
180 views

Find a ternary $4\times 39$ matrix satisfying the conditions below

Can you find a matrix $A_{4\times39}$ with elements from $\{-1,0,1\}$ so that No column is all zero. All columns are different. No column is $-1$ times another column. Each row consists of $13$ of ...