0
votes
0answers
26 views

Algorithmic Complexity of Linear Independence

Given n m-dimensional vectors. You can determine linear independence by Gaussian elimination. http://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency Checking linear independence ...
1
vote
0answers
46 views

number of multiplication steps required to solve Ax = b

If we can factorize $A$ in $LU$, We can solve $Ax = b$ in 2 steps: Solve $Lc = b$ for c Solve $Ux = c$ for x As per the Linear algebra book by Gilbert Strang, each step takes $n^2/2$ number of ...
0
votes
0answers
27 views

Matrix scaling problem for Unitary matrices

I would like to know about the complexity of the following problem. Given a ($n\times n$) unitary matrix U and two row-vectors R and C of rational numbers, all of which less than 1, with ...
1
vote
0answers
131 views

How to compute this recursion in linear time?

Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ ...
0
votes
1answer
16 views

Stability and complexity of some functions

Can someone check if my solutions/arguments on this exercise are correct? Thanks! Are the following statements true or false? $\sin (x)=\mathcal{O}(1)$ as $x \rightarrow \infty$ $\sin ...
2
votes
0answers
60 views

Asymptotic behavior of $L^2$ norm for increased matrix dimensions

I am playing with matrices which are linear combinations of identity matrix, Pauli spin matrices, $\sigma_x$ and $\sigma_z$ or their tensor products. For example, let the matrix be $H$. So, $H$ could ...
0
votes
0answers
34 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
7
votes
1answer
115 views

complexity of matrix multiplication

For $n\times n$ dimensional matrices, it is known that calculating $\operatorname{tr}\{AB\}$ needs $n^2$ scalar multiplications. How many scalar multiplications are needed to calculate ...
6
votes
3answers
266 views

Which is easier to work out: determinant or inverse?

Suppose $A\in M_n(R)$ be a $n\times n$ matrix over some ring $R$. Which of the following two tasks is easier? to work out $\det(A)$; to work out $A^{-1}$. More specifically, I want to know the ...
0
votes
2answers
75 views

How to work out the inverse matrix $A^{-1}$ ?

Suppose A is a matrix over some ring R (might be non-commutative). How to work out the inverse matrix $A^{-1}$?
6
votes
2answers
1k views

Minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
5
votes
1answer
169 views

Complexity of a quadratic program

I have a quadratic program: $$\displaystyle\min_{\mathbf{X}} (\mathbf{X^TQX +C^TX}) \quad{} \text{subject to} \quad{} \mathbf{A X \leq Y}$$ $\mathbf{Q}$ is positive definite and is $N \times N$, ...
4
votes
1answer
135 views

In terms of complexity, is there a quicker way of checking if a matrix is nonsingular than computing the determinant?

To repeat the question, let $A$ be a square matrix. We wish to determine if $A$ is nonsingular, that is, invertible. One way is compute its determinant and check if it is nonzero. However, if $A$ is ...
4
votes
3answers
97 views

What would be complexity of computing $3^{n^n}$?

Just curious, what would be the computational complexity of computing $3^{n^n}$? I am not sure what it would be like.
0
votes
1answer
92 views

How can I do this kind of Cholesky decomposition?

$B_{(n+1)(n+1)}$ = $ \begin{bmatrix} A & u \\ u^T & 1 \\ \end{bmatrix}$ = $\begin{bmatrix} L_{11} & 0 \\ L_{21} & l_{22} \\ ...
0
votes
2answers
244 views

Inverse of matrix with QR method

What is the complexity of finding the inverse of matrix by QR decomposition? A is a $n×n$ with full rank.
2
votes
0answers
113 views

matrix construction

Given any matrix $A$, can one construct a matrix $B$ such that $B$ is nonnegative and the spectral radius of $B$ is strictly less than 1 the determinant of $A$ is equal to the first entry of $B^*$ ...
2
votes
1answer
171 views

Complexity of Gauss elimination over ring $Z_n.$

Is there some polynomial upper-bound for Gauss elimination over ring $Z_n$? I'm interested in polynomial bound depending from size of matrix and $\log n$. I also have the same question about the ...
2
votes
0answers
261 views

Proving that basic linear algebra problems (LINEQ and Linear Programming) are in NP

I'm working through the problems in Arora & Barak's textbook on Computational Complexity. It's all been good so far, but I'm kind of stuck on this pair of problems in Chapter 2 (2.3 and 2.4). I'm ...
5
votes
0answers
416 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
3
votes
2answers
388 views

equivalence between matrix multiplication and matrix inversion

I am a bit confused with this wikipedia article, hoping someone can clarify it. Looking at the Strassen algorithm page it is clear that this is an algorithm for reducing multiplication operations. ...
9
votes
2answers
642 views

Has there been a rigorous analysis of Strassen's algorithm?

According to Wikipedia, Strassen's Algorithm runs in $O(N^{2.807})$ time. Has anyone seen a more rigorous analysis displaying constants, possibly in a specific language such as C or Java? I ...
1
vote
1answer
854 views

Gauss Jordan elimination - count of steps for $N \times M$ equation

I am having some problem wrapping my head around an assignment. I have to find out how many additions, subtractions, multiplications and divisions are used while solving an $N \times M$ linear ...