Question

Let M be an n x n matrix with each entry equal to either 0 or...

Let M be an n x n matrix with each entry equal to either 0 or 1. Let mij denote the entry in row i and column j. A diagonal entry is one of the form mii for some i.

Swapping rows i and j of the matrix M denotes the following action: we swap the values mik and mjk for k = 1,2, ... , n. Swapping two columns is defined analogously.
We say that M is rearrangeable if it is possible to swap some of the pairs of rows and some of the pairs of columns (in any sequence) so that, after all the swapping, all the diagonal entries of M are equal to 1.

(a) Give an example of a matrix M that is not rearrangeable, but for wbich at least one entry in each row and each column is equal to 1.
(b) Give a polynomial-time algorithm that determines whether a matrix M with 0-1 entries is rearrangeable.

Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

* Please provide feedback if it clarifies your doubt.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let A be an n×n matrix, I be n×n identity matrix. Define Lij =I+Mij, (1) i...
Let A be an n×n matrix, I be n×n identity matrix. Define Lij =I+Mij, (1) i > j, where the only non-zero element of Mij is mij on i-th row, j-th column. 1. Calculate LijA. What is the relationship between LijA and A? 2. Calculate L−1. ij 3. Suppose now we have a series of nonzero real numbers mi+1,i, mi+2,i, · · · , mn,i. Define Li+1,i , Li+2,i , · · · , Ln,i in the fashion of equation...
Let T be an linear transformation from ℝr to ℝs. Let A be the matrix associated...
Let T be an linear transformation from ℝr to ℝs. Let A be the matrix associated to T. Fill in the correct answer for each of the following situations (enter your answers as A, B, or C).   1. Every row in the row-echelon form of A has a leading entry.   2. Two rows in the row-echelon form of A do not have leading entries.   3. The row-echelon form of A has a leading entry in every column.   4. The row-echelon...
Let M=[[116,−48],[−48,44]]. Notice that 20 is an eigenvalue of M. Let U be an orthogonal matrix...
Let M=[[116,−48],[−48,44]]. Notice that 20 is an eigenvalue of M. Let U be an orthogonal matrix such that (U^−1)(M)(U) is diagonal, the first column of U has positive entries, and det(U)=1. Find (√20)⋅U.
9. Suppose AB is defined and you know all the entries in both matrices.                a)...
9. Suppose AB is defined and you know all the entries in both matrices.                a) Find the entry in row i and column j of AB                b) Write column j of AB as a linear combination of columns of A.                c) Write row i of AB as a liner combination of rows of B                d) If A is size m×n and B is size x p , write AB as the sum of n matrices of...
1. Let a,b,c,d be row vectors and form the matrix A whose rows are a,b,c,d. If...
1. Let a,b,c,d be row vectors and form the matrix A whose rows are a,b,c,d. If by a sequence of row operations applied to A we reach a matrix whose last row is 0 (all entries are 0) then:        a. a,b,c,d are linearly dependent   b. one of a,b,c,d must be 0.       c. {a,b,c,d} is linearly independent.       d. {a,b,c,d} is a basis. 2. Suppose a, b, c, d are vectors in R4 . Then they form a...
Let matrices A,B∈Mn×n(R). Show that if A and B are each similar to some diagonal matrix,...
Let matrices A,B∈Mn×n(R). Show that if A and B are each similar to some diagonal matrix, and also have the same eigenvectors (but not necessarily the same eigenvalues), then  AB=BA.
Part 2: Solve the following problems in MATLAB 1. Fill in the function E = myElim(A,...
Part 2: Solve the following problems in MATLAB 1. Fill in the function E = myElim(A, r_entry, r_pivot, c) to create an m by m elimination matrix ??. Remember that an elimination matrix looks like an identity matrix with one extra entry of ?? in row r_entry and column r_pivot. 2. Fill in the function M = myMult(A, c_pivot) to create an m by m multiplier matrix ??. Remember that a multiplier matrix looks like an identity matrix with the...
(a) Consider binary codes determined by a parity-check matrix H. Let r be a vector of...
(a) Consider binary codes determined by a parity-check matrix H. Let r be a vector of received symbols. The syndrome of r happens to be a sum of some columns of H. What columns are these? Hint: They are determined by the errors occurring in transmissions. (b) Let G be a k × n generating matrix of a code C the form G = [I_k | B] , where Ik is the k × k identity matrix, and B is...
Recall that if A is an m × n matrix and B is a p ×...
Recall that if A is an m × n matrix and B is a p × q matrix, then the product C = AB is defined if and only if n = p, in which case C is an m × q matrix. (a) Write a function M-file that takes as input two matrices A and B, and as output produces the product by columns of the two matrix. For instance, if A is 3 × 4 and B is...
a)Assume that you are given a matrix A = [aij ] ∈ R n×n with (1...
a)Assume that you are given a matrix A = [aij ] ∈ R n×n with (1 ≤ i, j ≤ n) and having the following interesting property: ai1 + ai2 + ..... + ain = 0 for each i = 1, 2, ...., n Based on this information, prove that rank(A) < n. b) Let A ∈ R m×n be a matrix of rank r. Suppose there are right hand sides b for which Ax = b has no solution,...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT