We are given an n × n matrix A = (aij ) with non-negative entries, and we are interested in the question of whether it can be expressed as a sum of two n × n matrices R, C such that: (1) The entrices of C and R are non-negative; (2) The row sums of R are bounded above by 1. (3) The column sums of C are bounded above by 1.When there exist matrices R, C satisfying these three constraints, such that R + C = A, let us call the pair (R, C) a row+column decomposition of A. (a) (7 points, you do not need to prove the correctness of your algorithm for this question) Design a polynomial-time algorithm (polynomial in n) which takes a non-negative matrix A as input, and either outputs a row+column decomposition or reports (correctly) that no such decomposition exists.

To determine if a row+column decomposition exists for a given matrix A, we can use the following algorithm:

1. Initialize two n × n matrices R and C as zero matrices.
2. For each row i of A, calculate the maximum possible value for the sum of that row in R while keeping all entries non-negative. Let this value be max_sum_i.
3. For each column j of A, calculate the maximum possible value for the sum of that column in C while keeping all entries non-negative. Let this value be max_sum_j.
4. If max_sum_i + max_sum_j < Aij for any entry (i, j) in A, then no row+column decomposition exists. Otherwise, proceed to step 5.
5. For each entry (i, j) in A, set Rij to the minimum of Aij and max_sum_i, and set Cij to the minimum of Aij and max_sum_j.
6. Return the row+column decomposition (R, C).

This algorithm runs in polynomial time in n because steps 2 and 3 can be computed in O(n^2) time, and steps 4 and 5 can be computed in O(n^2) time as well. Therefore, the overall runtime is O(n^2).